admin管理员组

文章数量:1446759

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

状态表示：

状态转移方程：

这里不知道则么推导看一看：链接: 点击

初始化：

填表顺序：

返回值：

这里是引用

代码呈现：

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public int coinChange(int[] coins, int amount) {

        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        int INF = 0x3f3f3f3f;//注意这题，找的是最小值，如果用-1表示会被更新进去导致错误

        for(int i = 1; i <= amount; i++) dp[0][i] = INF;

        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] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]]+1);//找的是最小值
            }

        return dp[n][amount] >= INF ? -1 : dp[n][amount];    

    }
}

优化版本：

这里不知道怎么优化可以看看：链接: 点击

代码语言：javascript代码运行次数：0运行复制
int n = coins.length;
        int[] dp = new int[amount+1];
        int INF = 0x3f3f3f3f;//注意这题，找的是最小值，如果用-1表示会被更新进去导致错误

        for(int i = 1; i <= amount; i++) dp[i] = INF;

        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= amount; j++){
                if(j >= coins[i-1]) 
                    dp[j] = Math.min(dp[j], dp[j-coins[i-1]]+1);//找的是最小值
            }

        return dp[amount] >= INF ? -1 : dp[amount];
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-12，如有侵权请联系 cloudcommunity@tencent 删除intmin动态规划优化dp

本文标签：

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