Получение неверного результата при применении подхода к меморизации DP в рекурсивной проблеме перекрытия - PullRequest
Новая
       6

Получение неверного результата при применении подхода к меморизации DP в рекурсивной проблеме перекрытия

0 голосов
/ 31 марта 2020

Я применял метод напоминания DP в рекурсивной проблеме Изменение монеты . Но я получаю неправильный ответ, применяя метод запоминания (подход сверху вниз), чтобы преодолеть проблему перекрытия.

Ниже приведено рекурсивное решение (которое дает правильный результат): 

#include<stdio.h>
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution
    // (do not include any coin)
     if(n==0)
        return 1;

    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

// Driver program to test above function
int main()
{
    int i, j;
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 4));
    getchar();
    return 0;
}

Ниже приведен код подхода к запоминанию, который я применил (даю неправильный ответ): 

#include<stdio.h>
int dp[100];
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution
    // (do not include any coin)
     if(n==0)
        return 1;

    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <=0 && n >= 1)
        return 0;

    //Memoization
    if(dp[n]!=0)
        return dp[n];

    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return dp[n] = count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

// Driver program to test above function
int main()
{
    int i, j;
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int u;
    dp[0]=1;
    for(u=1;u<=99;u++)
        dp[u] = 0;
    printf("%d ", count(arr, m, 4));
    getchar();
    return 0;
}

Я много проверял, где / что я делаю неправильно, но не смог найти его. Пожалуйста, помогите узнать ошибку. Спасибо:)

1 Ответ

2 голосов
/ 31 марта 2020

Вы пытаетесь запомнить результат для определенного значения n, но вы забываете m. Вам нужен двухмерный блокнот. Нечто подобное. 

int dp[100][100];
int count(int S[], int m, int n) {
    ...
    if (dp[n][m] != 0) return dp[n][m];
    dp[n][m] = count(S, m - 1, n) + count(S, m, n - S[m - 1]);
    return dp[n][m];
}

int main() {
    ...
    int u;
    for (int i = 0; i < 100; ++i) {
        dp[0][i] = 1;
        for (u = 1; u <= 99; u++) dp[u][i] = 0;
    }
    ...
    return 0;
}
...