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

题目： 

 思路：

 拿示例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

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

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

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

相关内容

热门资讯

关于《塘约道路》党员读后感大全... 导语：《塘约路途》指引我国村庄前进方向，塘约路途是有远见的当地领导干部率民众放下包袱、轻装上阵、齐心...
关于塘约道路读后感精选3篇最新... 　导语：《塘约路途》指引我国乡村前进方向，塘约路途是有远见的本地领导干部率民众放下包袱、轻装上阵、群...
《塘约道路》读后感1000字精... 　塘约路途读后感范文【1】　　《塘约路途》由陈述文学家、闻名专家王宏甲所创造，是记载贵州安顺一个穷山...
最新或2023（历届）党员干部... 导语：《塘约路途》由陈述文学家、闻名专家王宏甲所创造，是记载贵州安顺一个穷山村在党安排带领下，如何从...
最新或2023（历届）最新《套... 套中人读后感【篇一】　　读《套中人》令我感到《套中人》中的形象在现实中也是存在的，有人说《套中人》很...
最新《终结拖延症》读后感 终结... 最新《终结拖延症》读后感【篇一】　　之前一次参加果壳的赠书写书评的活动又一次赤裸裸的见证了我的拖延症...
《永生的眼睛》读后感【最新】 ... 永生的眼睛读后感【篇一】　　今天，我读了《永生的眼睛》，心里深受感动。　　课文主要讲了作者一家三代已...
最新或2023（历届）《野性的... 野性的呼唤读后感【篇一】　　野性的呼唤是一本很好的书，不像童话那样可爱生动活泼，有时候甚至是让人感到...
有关《金色的脚印》读后感 金色... 有关金色的脚印读后感【篇一】　　读了《金色的脚印》这篇文章，我才明白了狐狸并不是没有良心的，它们也有...
有关《森林报》读后感集锦 森林... 森林报读后感【篇一】　　最近我看了《森林报》，我觉得它很好看，森林报是一份特殊的报纸，它与其它报纸全...
儒商是中国梦的推动者读后感 儒... 儒商是中国梦的推动者读后感一：　　5月9日在学习了《儒商是中国梦的推动者》一文之后，感慨颇多：　　所...
反腐小说《人民的名义》读后感 ... 反腐小说《人民的名义》读后感【篇一】　　在官场文学的作品里，论文学性，周梅森的作品不如阎真的《沧浪之...
关于《美丽广州我的中国梦》读后... 《美丽广州我的中国梦》读后感【篇一】　　广州市爱国主义教育基地层次多样、内容丰富、分布广泛、影响力强...
最新或2023（历届）《狼王梦... 最新或2023（历届）狼王梦读后感600字【篇一】　　《狼王梦》是“动物小说大王”沈石溪写的一部关于...
老舍写的母鸡读后感精选 老舍的... 老舍写的母鸡读后感【篇一】　　今天我们学习了《母鸡》这篇课文，母鸡对她的小雏鸡关心，呵护让我很感动。...
读《米开朗琪罗传》有感 3篇 ... 读米开朗琪罗传有感【篇一】　　名人传中，介绍了三位伟人，分别是贝多芬、米开朗琪罗和托尔斯泰，米开朗琪...
关于革命先烈的英雄事迹读后感 ... 关于革命先烈的英雄事迹读后感【篇一】　　如果问是谁开创了中国历史的先河，我会回答：革命先烈们。他们用...
《普法教育读本》读后感精选 普... 《普法教育读本》读后感【篇一】　　我们从小就接受法制教育, 享受法律给予的权利.但是在事实上到底有多...
最新《青少年普法教育读本》读后... 《青少年普法教育读本》读后感【篇一】　　《全国青少年普法教育读本》，这本书，始终让我记忆犹新。因为，...
读《百年追梦全面小康》有感 读... 读《百年追梦全面小康》有感一：　　根据我国经济社会发展实际，党的十六大、十七大都确立了全面建设小康社...