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

Question

I've solved Leetcode's Coin Change 2 problem with a DFS + memoization approach in Python, with the solution below

# 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)

As a C++ newbie I've been practising my C++ by converting my Leetcode Python solution into a C++ one. This is what I've done:

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);
}

I cannot for the life of me figure out why my C++ solution is not passing all the test cases like my Python solution did. I feel like my lack of knowledge on C++ is making it difficult for me to figure out why my C++ implementation is wrong.

An example of a test case:

5
[1,2,5]

should return 4.

Answer 1

Your memoization in the C++ solution looks at index and amount (a constant), when your Python one looks at index and a.

Changing it accordingly fixes it, i.e

[...]

    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];

[...]