动态规划完全背包系列一＞零钱兑换II

状态表示：

状态转移方程：

初始化：

填表顺序：

返回值：

返回dp[n][amount]

代码：

代码语言：javascript代码运行次数：0运行复制

class Solution {
    
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        dp[0][0] = 1;


        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= amount; j++){
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1]){
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }

        return dp[n][amount];                
    }
}

空间优化版本：

不知道优化看：链接: 点击

代码语言：javascript代码运行次数：0运行复制

class Solution {

    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;


        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= amount; j++){
                if(j>=coins[i-1]){
                    dp[j] = dp[j] + dp[j-coins[i-1]];
                }
            }

        return dp[amount];                
    }
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-21，如有侵权请联系 cloudcommunity@tencent 删除前往查看intpublic动态规划优化dp