La respuesta incorrecta de la subsecuencia creciente más larga.
Escribí una solución recursiva para la subsecuencia más larga creciente y funcionó perfectamente bien. Pero cuando apliqué dp en el mismo código, dio respuestas diferentes.
Enlace al problema: https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence-1587115620/1
Código recursivo:
int LISrecursive(int arr[], int n, int currIndex, int maxVal) {
if (currIndex == n) {
return 0;
}
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 + LISrecursive(arr, n, currIndex + 1, arr[currIndex]);
}
notIncluded = LISrecursive(arr, n, currIndex + 1, maxVal);
return max(notIncluded, included);
}
Código DP:
int LISdp(int arr[], int n, int currIndex, int maxVal, vector<int> &dp) {
if (currIndex == n) {
return 0;
}
if (dp[currIndex] != -1) return dp[currIndex];
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 + LISdp(arr, n, currIndex + 1, arr[currIndex], dp);
}
notIncluded = LISdp(arr, n, currIndex + 1, maxVal, dp);
return dp[currIndex] = max(notIncluded, included);
}
int32_t main() {
int n;
cin >> n;
int arr[n];
vector<int> dp(n, -1);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << LISrecursive(arr,n,0,-1);
cout << LISdp(arr, n, 0 , -1, dp);
return 0;
}
¡No puedo averiguar qué hice mal!
Para este caso de prueba
6 (n)
6 3 7 4 6 9 (arr [])
El código recursivo da una respuesta de 4 (correcta)
Pero el código DP da una respuesta de 3 (incorrecta)
davy.ai
El problema con el código DP es que los valores en el vector dp no se están actualizando correctamente. En el caso base de la función recursiva, el valor devuelto es 0. Sin embargo, en el código DP, si dp [currIndex]! = -1, entonces la función devuelve dp [currIndex], lo cual es incorrecto ya que podría ser 0.
Para solucionar este problema, deberíamos cambiar el caso base en el código DP para devolver 1 en lugar de 0, ya que la longitud mínima de cualquier subsecuencia es 1. El código DP actualizado se vería así:
Con este cambio, el código DP debería funcionar correctamente y devolver la misma respuesta que el código recursivo para el caso de prueba dado.