爬楼梯问题:
实际是求排列数。即:对于爬上3层,先2后1和先1后二是两种不同的方法。
状态定义:dp[i] 表示到达第i层的方法有多少种。
状态转移:dp[i] = dp[i – 1] + dp[i- 2];
零钱兑换问题:
实际是组合数问题。即:要凑3块钱,先选择2块还是先选择1块的零钱都只算1种方法。
子问题定义:对于硬币从0到k,必须使用第k个硬币时当前金额的组合数。
状态定义:dp[i]表示对于选择第k个硬币时凑到金额i的组合数。
状态转移:dp[i] = dp[i] + dp[i – coin[k]];
关键:因为外循环时先遍历硬币种类数,所以其实这里规定了硬币的顺序,即排除了同样组合硬币的其他排列方式。