algorithm - DP中的硬币制作问题 - 使用二维备忘录表得到错误答案

Question

当我通过这个输入时，我得到了错误的答案

硬币[] = {5,6}

数量(W) = 10

我的答案 = 1

正确答案应该是 2 即 {5,5}

void coin_make(int W, vector<int> coin){

int n = coin.size();
int dp[n+1][W+1];


for(int i = 0; i <=W; i++){
    dp[0][i] = INT_MAX;
}

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= W; j++){

        if(coin[i-1] == j){
            dp[i][j]  = 1;
        }
        else if(coin[i-1] > j){
            dp[i][j] = dp[i-1][j];
        }
        else {
            dp[i][j] = min(dp[i-1][j], 
                        1 + dp[i][j-coin[i-1]]);
        }
    }
}
cout<<dp[n][W];}

标签： algorithmdynamic-programmingcoin-change

Answer 1

你已经溢出来了dp[1][6]，因为你试图计算1 + INT_MAX。此错误进一步传播，最终答案不正确。当我在我的机器上运行它时，我得到了-2147483648. 您应该使用其他一些常量作为“无穷大”来防止溢出（例如2e9（或-1，但这需要一些额外if的语句））。然后代码将在您提供的测试用例上正常工作。