力扣70题 动态规划思想题目大意每次爬1或2阶问爬到第n阶有多少方法。例1阶11种2阶11和22种。现在n 3有几种爬法列举一下1 1 1、2 1、1 2所以总共有三种。现在n 4有几种爬法列举一下1 1 1 1 、2 1 1、1 1 2、1 2 1、2 2所以总共有5种。n 5呢……为了节约时间当n 5时总共有8种爬法。如果一一列举则显得麻烦换种思路想想当n 3时有两种情况我刚才在第2阶迈一步上来还有我刚在第1阶迈两步上来。那我怎么走到第2阶可以1阶1阶走也可以直接2阶所以当n 3时有3种情况。换成数学表达式f(3) f(2) f(1)。看看n 4在到达4阶之前我只能站在第3阶或者第2阶上那走到3阶有3种方法走到2阶有2种方法。换成数学表达式f(4) f(3) f(2)……动态规划思想根据上述分析我们得出“状态转移方程”为f(n) f(n-1) f(n-2)但如果我们采用递归方式去进行计算这个式子会发现时间消耗的比较多举个例子假如我们要算f(5)就要先知道f(4)和f(3)f(4)又要算f(3)和f(2)f(3)被算了两次更别说n越大重复的计算次数就越多。这时候动态规划的“以空间换时间”思想就可以体现我们采用“自底向上”的方法将算过的值存储起来。事实上我们当然可以用数组将算过的值存起来但这道题只需要知道n前面两个数对应的值其余的值我们可以不存。这里引出滚动变量思想这个思想与两个变量的值进行交换的思想一致。我们用a表示f(n - 2)b表示f(n - 1)c表示f(n)当n 3时a f(n - 2)为f(1)b f(n - 1)为f(2)当n 4时a f(n - 2)为f(2)b f(n - 1)为f(3)就是说将b的值赋给了a将c赋给了b这就能实现滚动的效果。完整代码classSolution(object):defclimbStairs(self,n): :type n: int :rtype: int ifn2andn0:returnnelse:a1b2foriinrange(3,n1):cab a,bb,creturnb细节注意这里其实我们并没有在外面定义c这个变量因为c相当于是临时工的作用它仅仅是将结果交给b我们最终返回的是b。但其实也可以定义c但那样会多浪费一个空间。当然也可以返回循环里的c但b因为在循环外定义过更安全所以我们返回b。