【刷题笔记】--dp--零钱兑换Ⅱ
创始人
2025-05-31 19:44:55

题目： 

 思路：

 拿示例1来看，我们的原问题是求dp[5]，表示金钱为5时，凑出该金额的硬币组合数，子问题自然就是dp[1]，dp[2]，dp[3]，dp[4]，现在的问题就是找到子问题与原问题的关系。

dp[5]是不是可以表示为当金额为4时的硬币组合后面都加上硬币1+当金额为3时的硬币组合后面都加上硬币2+当金额为0时的硬币组合后面都加上硬币1

即dp[5]=dp[4]+dp[3]+dp[0]（原理就是依次让5减去，coins数组里面的每一个数）

但是有个问题，就是会有重复组合的情况出现。

举个更简单的例子，

我们很容易知道dp[1]=1;（1）

                         dp[2]=2;（1+1或2）

如果按上面推理：dp[3]=dp[3-1]（2+1）（1+1+1）+dp[3-2]（1+2）=3;

 但很显然dp[3]=2 (1+1+1或1+2）

按上面的思路就是写两个for循环代码：

for(i=1;i

        for(j=0;j

                dp[i]+=dp[i-coins[j]];

        }

}

那要如何避免就是重复的问题呢？

看了别人的题解：发现他们的两个for循环和我的是对调的。即：

for(int i=0;i

 对于上面这个代码的理解，举个例子，对于dp[3]的计算，

dp[3]=dp[2] (1+1+1）       i=0的循环下

dp[3]=dp[1](1+2)              i=1的循环下

所以dp[3]=2;

所以就不会重复计算dp[3]=(2+1)

代码：

class Solution {public int change(int amount, int[] coins) {int[] dp=new int[amount+1];//定义一个dp数组dp[0]=1;for(int i=0;i

上一篇：从命令行向’git commit -m’添加换行符------转

下一篇：什么是队列，如何实现？

相关内容

热门资讯

三街七巷笔记 （来源：衢州日报）转自：衢州日报　　周维强　　月落天王塔　　古街如琵琶，那琴弦，被时光仙子　　捏在手...
无锡有什么好玩的地方,最新或2... 古运河横贯于无锡市的古运河段以吴桥为起点经西水墩、南门至清名桥，河段虽仅有6公里却最具江南味。这里有...
南京有什么好玩的地方,最新或2... 南京位于江苏省西部，东依宁镇山脉，地势险固，风景秀丽。南京是历经苍桑的十代都会。三国鼎立，她目睹群雄...
江苏有什么好玩的地方,最新或2... NO.1 中山陵中山陵是孙中山的陵墓，位于南京东郊的钟山风景区内，东毗灵谷寺，西邻明孝陵。整个建筑群...
葫芦岛有什么好玩的地方,最新或... 葫芦岛市 葫芦岛市1989年建市，原名锦西市。是环渤海经济圈最年轻的城市。东邻锦州，西接山海...