Climb Stairs类DP

应用

climb stairs本质上也是求subset sum的背包问题。这个问题翻译成背包问题的语言就是，在n种steps里面，取出一些steps，每种step可以无限制的选择，放入一个stairs长度大小的背包里，总共有多少取法。而climb stairs问题和01背包以及完全背包的区别在于，这里取东西的sequence matters，而01、完全背包取东西的sequence不matter。

状态定义和状态转移

DP问题最重要的就是状态定义和状态转移方程。

状态定义：对于前n步台阶，有多少种走法可以走完。／对于前n个chars，有多少种方法可以decode。

状态转移：我们考虑转移方程，都是考虑当前规模的问题如何和更小规模的子问题联系起来。这里如果台阶的选择步数有三步，那么我们可以表示为dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]，当然这些数得是 >= 0。

题目

• Leetcode 91. Decode Ways
• Leetcode 70. Climbing Stairs
• Leetcode 377. Combination Sum IV