这个使用带记忆的 DFS 的 Coin Change 解决方案有什么问题？

Question

我在 Python 中用 DFS + memoization 方法解决了 Leetcode 的 Coin Change 2 问题，解决方案如下

# O(m*n)
def change(amount: int, coins: List[int]) -> int:
    cache = {}
    
    def dfs(i, a):
        if a == amount:
            return 1
        
        if a > amount:
            return 0
        
        if i == len(coins):
            return 0
        
        if (i, a) in cache:
            return cache[(i, a)]

        cache[(i, a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)
        
        return cache[(i, a)]
    
    return dfs(0, 0)

作为 C++ 新手，我一直在通过将我的 Leetcode Python 解决方案转换为 C++ 解决方案来练习我的 C++。这就是我所做的：

int dfs(int index, int a, int amount, vector<int> coins, vector<vector<int>>& dp) {
    if (a == amount) {
        return 1;
    }
    if (a > amount) {
        return 0;
    }
    if (index == coins.size()) {
        return 0;
    }
    
    if (dp[index][amount] != -1) {
        return dp[index][amount];
    }
    
    dp[index][amount] = dfs(index, a + coins[index], amount, coins, dp) + dfs(index + 1, a, amount, coins, dp);

    return dp[index][amount];
}

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    vector<vector<int>> dp(n,vector<int>(amount+1, -1));
    return dfs(0, 0, amount, coins, dp);
}

我一辈子都弄不明白为什么我的 C++ 解决方案没有像我的 Python 解决方案那样通过所有测试用例。我觉得我对 C++ 知识的缺乏让我很难弄清楚为什么我的 C++ 实现是错误的。

测试用例示例：

5
[1,2,5]

应该return4.

Answer 1

您在 C++ 解决方案中的记忆化查看 index 和 amount（常量），而您的 Python 则查看 index 和 a .

相应地更改它可以修复它，即

[...]

    if (dp[index][a] != -1) {
    return dp[index][a];
}

dp[index][a] = dfs(index, a + coins[index], amount, coins, dp) + dfs(index + 1, a, amount, coins, dp);

return dp[index][a];

[...]

这个使用带记忆的 DFS 的 Coin Change 解决方案有什么问题？

What is wrong with this Coin Change solution using DFS with memoization?

c++

memoization

depth-first-search