动态规划基本步骤[亲测有效]

动态规划基本步骤[亲测有效]第一步,确定问题状态动态规划问题求解需要先开一个数组,并确定数组的每个元素f[i]代表什么,就是确定这个问题的状态。类似于解数学题中,设定X,Y,Z代表什么。a.确定状态首先提取最优策略必定是K枚硬币a1,a2,…,aK面值加起来是27。找出不影响最优策略的最后一个独立角色,这道问题中,那枚最后的硬币“aK”就是最后一步。把aK提取出来,硬币aK之前的所有硬币面值加总是27-aK因为总体求最硬币数量最小策略,所以拼出27-aK的硬币数也一定最少转化子问题如果aK是2,f(27)

大家好,欢迎来到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

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信