3 DP variants in C++


  • 0
    C
        int dp2(int amount, vector<int>& coins) {
            int n = coins.size();
            vector<vector<int>> dp(amount + 1, vector<int>(n + 1));
            for(int j = 0; j <= n; ++j)
                dp[0][j] = 1;
            for(int i = 1; i <= amount; ++i) {
                for(int j = 1; j <= n; ++j) {
                    //exclude jth coin and include jth coin(iff its more than current amount i)
                    dp[i][j] += (dp[i][j-1] + (i >= coins[j-1] ? dp[i - coins[j-1]][j] : 0));
                }
            }
            return dp[amount][n];
        }
        int dp2b(int amount, vector<int>& coins) {
            int n = coins.size();
            vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
            dp[0][0] = 1;
            for(int i = 1; i <= n; ++i) {
                dp[i][0] = 1;
                for(int j = 1; j <= amount; ++j) {
                    dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
                }
            }
            return dp[n][amount];
        }
        int dp1(int amount, vector<int>& coins) {
            vector<int> dp(amount + 1);
            dp[0] = 1;
            for(auto coin : coins) {
                for(int i = coin; i <= amount; ++i)
                    dp[i] += dp[i - coin];
            }
            return dp.back();
        }
        int change(int amount, vector<int>& coins) {
            //return dp2(amount, coins);
            //return dp2b(amount, coins);
            return dp1(amount, coins);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.