admin管理员组

文章数量:1035890

动态规划完全背包系列一＞零钱兑换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

动态规划完全背包系列一＞零钱兑换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

本文标签： 动态规划完全背包系列一＞零钱兑换II

版权声明：本文标题：动态规划完全背包系列一＞零钱兑换II 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748194515a2267392.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。