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

用户11305962

发布于 2025-03-22 09:10:38

3400

代码可运行

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

运行总次数：0

代码可运行

状态表示：

状态转移方程：

初始化：

填表顺序：

返回值：

返回dp[n][amount]

代码：

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];                
    }
}

空间优化版本：

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

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

int