动态规划基本步骤_动态规划的布置

第一步，确定问题状态

动态规划问题求解需要先开一个数组，并确定数组的每个元素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];
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19