动态规划理论基础，LeetCode 509. 斐波那契数 LeetCode 70. 爬楼梯 LeetCode 746. 使用最小花费爬楼梯

LeetCode 509. 斐波那契数

思路

动态规划五部曲：

Code

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""dp = [0] * (n+1)  ## dp数组的初始化，且确保总能获取到F(n)，F(n)的最小数组长度为n+1if n >= 1:dp[1] = 1if n == 0:      ## 特殊情况处理return 0elif n == 1:return 1length = len(dp)for i in range(2,length):     ### 左闭右开，遍历顺序dp[i] = dp[i-1] + dp[i-2] ### 遍历公式 + dubug查看dp数组return dp[n]

LeetCode 70. 爬楼梯

思路

回溯算法也可以解决，但会存在超时的问题。Code如下：

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""self.path = []self.total = 0self.sum = 0nums = [1, 2]self.backtracking(nums, n, 0)return self.sumdef backtracking(self, num, n, start_index):if self.total == n:self.sum += 1return if self.total > n:return for i in range(start_index, len(num)):self.path.append(num[i])# print("self.path", self.path)self.total += num[i]# print("self.total", self.total)self.backtracking(num, n, 0)self.total -= num[i]self.path.pop()

这道题的题目关键不是在于排序组合的获取（即你走到这阶台阶的过程），而是在于迈向更高台阶方法数目和低台阶方法数目的联系。

从上述方法数目我可以看得出到第N阶的方法总数F(N)其实就是F(N-1)+F(N-2) —— 递归公式。

为什么会有这种规律。因为迈的步子只为1和2，因此如果你迈的步子为2，那么从F(N-2)迈向F(N)，可以通过只迈2步实现，因此F(N)的方法总数中包含了F(N-2)。另外，如果你迈的步子为1，那从F(N-1)迈向F(N)可以通过只迈一步实现，可以F(N)的方法总数中包含了F(N-1)，这就是为什么是F(N) = F(N-1) + F(N-2)。

递归五部曲：

Code

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""dp = [0] * nif n == 1:return 1if n >= 1:dp[0] = 1   ## 迈向第一级台阶的方法数目dp[1] = 2   ## 迈向第二级台阶的方法数目length = len(dp)for i in range(2,length):dp[i] = dp[i-1] + dp[i-2]return dp[n-1]

其实递推公式和遍历顺序跟斐波那契数是一样的，只不过在数组长度初始化和前两个值的初始化上有区别。

LeetCode 746. 使用最小花费爬楼梯

容易陷入贪心的思路，即每次只与前面的元素的判断，通过大小来选择局部最优。如下所示：

[1,100,1000,200]。如果贪心思路的话，你前两个元素就会选择1，指针右移一位，后续选择100，指针右移后续选择200，这样的话总cost == 301，但实际上，从100可以直接到200，总cost == 300。

动规五部曲：

Code

class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""### 到达超出数组长度的下标就是到达楼梯顶部了。length = len(cost)dp = [0] * lengthif length > 2:for i in range(2, length):dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])### 距离楼梯顶部差一个台阶 / 两个台阶时需要进行比较     one_step_cost = dp[length-1] + cost[length-1]two_step_cost = dp[length-2] + cost[length-2]if one_step_cost > two_step_cost:return two_step_costelse:return one_step_cost