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

用户11305962

发布于 2025-03-13 08:31:19

400

代码可运行

文章被收录于专栏：学习学习

运行总次数：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];    

    }
}

优化版本：

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

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.com 删除

int