大家好,欢迎来到IT知识分享网。
第一步,确定问题状态
动态规划问题求解需要先开一个数组,并确定数组的每个元素f[i]代表什么,就是确定这个问题的状态。
类似于解数学题中,设定X,Y,Z代表什么。
a.确定状态首先提取
最优策略必定是K枚硬币a1, a2,…, aK 面值加起来是27。
找出不影响最优策略的最后一个独立角色,这道问题中,那枚最后的硬币“aK”就是最后一步。
把aK提取出来,硬币aK之前的所有硬币面值加总是27- aK
因为总体求最硬币数量最小策略,所以拼出27- aK 的硬币数也一定最少
转化子问题
如果aK是2,f(27)应该是f(27-2) + 1 (加上最后这一枚面值2的硬币)
如果aK是5,f(27)应该是f(27-5) + 1 (加上最后这一枚面值5的硬币)
如果aK是7,f(27)应该是f(27-7) + 1 (加上最后这一枚面值7的硬币)
至此,通过找到原问题最后一步,并将其转化为子问题。
为求面值总额27的最小的硬币组合数的状态就形成了,用以下函数表示:
f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
第二步,转移方程,把问题方程化。
f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
(动态规划都是要开数组,所以这里改用方括号表示)
第三步,按照实际逻辑设置边界情况和初始条件。
【必做】否则即使转移方程正确也大概率无法跑通代码。
也就是确立问题初始值,这是动态规划无法推测的
第四步,确定计算顺序并计算求解
public int coinChange(int[] coins, int amount) {
if (amount==0) return 0;
if (amount < 0) return -1;
/** 比如你想求 amount = 11 时的最少硬币数(原问题), 如果你知道凑出 amount = 10 的最少硬币数(子问题), 你只需要把子问题的答案加一(再选一枚面值为 1 的硬币)就是原问题的答案。 因为硬币的数量是没有限制的,所以子问题之间没有相互制,是互相独立的。*/
int[] dp=new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0]=0;
for (int i = 0; i <dp.length; i++) {
for(int coin:coins){
if (i-coin<0) continue;
dp[i]=Math.min(dp[i],1+dp[i-coin]);
}
}
//如果最后两个不相等,表示无法使用里面的硬币兑换
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/24391.html