[数据结构与算法]不同类型的动态规划问题简单区分

目前，就动态规划已经与到了很多类型的题目但现在最难理解的还是一下两个问题。
零钱兑换2 这个问题就是让我们求满足所给整数的零钱组合。
爬楼梯 但这个问题需要稍微做一下变式，我们能爬的阶数不仅仅局限于1和2了。给定我们一个非空数组，数组内的所有数字都是我们能够直接爬的阶数。。求能爬上顶点的方案
这两个问题显然都能利用动态规划的思想去解决。其代码完成后的差别也仅在内外循环的先后顺序
循环顺序的改变影响的是动态数组更新方式的不同。
第一题代码

class Solution {
    public int change(int amount, int[] coins) {
        int count=0;
        if(coins[0]==amount){
            return 1;
        }
        int dp[]=new int[amount+1];
        for(int i=0;i<dp.length;i++){
            dp[i]=0;
        }
        dp[0]=1;
        for(int j=0;j<coins.length;j++){
            for(int i=1;i<dp.length;i++){
                if(i>=coins[j]){
                    dp[i]+=dp[i-coins[j]];
                }
            }
        }
        return dp[amount]==0?0:dp[amount];
    }
}

可以想象这个一个特例帮助理解，给定我们的整数10以及coins数列｛5｝。由于所求的是方案数。我们想要排除由于多次循环j导致coin[j]产生顺序的影响。聪明的做法是把硬币数组的循环放在外面。回到那个特例，直到i=5时才满足i>=coins[j]。让dp[5]=1。后面的的dp[10]=dp[5]+1=2。以此类推,可以发现，要更新dp[i]就一定要使用当前的这个coin[j]。要不然你就别更新。**一趟下来所有dp[i]都已经更新成了需要当前这个coin[j]的方案数。**随后j++一同样的方式去继续更新dp[i]。上一个硬币值不会再重复使用了。也可以简单理解为我们按照coins数组的顺序来使用硬币凑数，这样想也是基于避免重复。
第二题代码

在这里插入代码片

这里的循环刚好与上一个题相反，原因在于这个题要有顺序。对于每一个dp[i]我们用尽全部的step[j]来进行赋值。·最终得到的也是带有顺序的排序数。