Вычисление LIS (самой длинной возрастающей подпоследовательности) в массиве - очень известная проблема динамического программирования. Однако в каждом руководстве они сначала показывают рекурсивное решение без использования концепций DP, а затем решают его, применяя DP снизу вверх (итеративное решение).
У меня вопрос:
Как мы будем использовать мемоизацию в самом рекурсивном решении. Не только мемоизация, но и мемоизация с использованием 1D-массива.
Я провел небольшое исследование, но не нашел ничего подходящего. Хотя есть 2 места, где запрашивалась рекурсивная мемоизация, 1 & 2, но решения там используют 2D-карту / массив для запоминания.
В любом случае запоминание решения с помощью одномерного массива дает неправильный результат. Вот что я сделал:
int lis(int idx, int prev)
{
if(idx >= N)
return 0;
if(dp[idx])
return dp[idx];
int best_ans = lis(idx+1, prev);
int cur_ans = 0;
if(arr[idx] > prev)
{
cur_ans = 1 + lis(idx+1, arr[idx]);
}
int ans = max(best_ans, cur_ans);
dp[idx] = ans;
return ans;
}
int main()
{
// Scan N
// Scan arr
ans = lis(0, -1));
print ans;
}
Хотя я знаю причину, по которой это решение дает неправильный результат:
Для данного индекса может быть несколько решений, основанных на предыдущем значении.
Но я все еще хочу знать, как это можно сделать с помощью одномерного массива.
Мне любопытно узнать решение, потому что я прочитал, что каждое решение DP сверху-вниз может быть преобразовано в снизу-вверх и наоборот.
Было бы очень полезно, если бы кто-нибудь мог дать некоторое представление о том же.
Заранее спасибо.
