LeetCode 509. 斐波那契数

思路

动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义。

一个数组，下标表示序列从哪里开始。

2. 确定递推公式

F(n) = F(n-1) + F(n-2)

3. dp数组如何初始化

下标0和下标1需要进行默认初始化，后续下标为n的元素需要通过下标为n-1和n-2的元素相加得到。dp数组长度等于n+1。

4. 确定遍历顺序

遍历顺序：下标从小到大进行遍历。

5. 举例推导dp数组

print递推后dp数组

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()

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

台阶	方法数目
1阶	1种方法( [1] )
2阶	2种方法( [1,1], [2] )
3阶	3种方法( [1,1,1], [1,2], [2,1])
4阶	5种方法( [1,1,1,1], [1,2,1], [2,1,1], [1,1,2], [2,2])
...	...

从上述方法数目我可以看得出到第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)。

递归五部曲：

1. 确定dp数组（dp table）以及下标的含义。

下标为0，表示迈1阶。因此迈的阶数 = 下标 + 1。

2. 确定递推公式

F(N) = F(N-1) + F(N-2)

3. dp数组如何初始化

因为后续相加是涉及到N-1和N-2，因此前两个元素需要手动初始化。dp数组的长度 == 阶数（n）。

4. 确定遍历顺序

从前向后遍历更新dp数组。

5. 举例推导dp数组

print递推后dp数组

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。

动规五部曲：

1. 确定dp数组（dp table）以及下标的含义。

dp[i]表示跳到第 i 个台阶时需要花费的cost。

2. 确定递推公式

dp[i] = min( dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) 即判断表示从第i-1个台阶出发跳1个台阶的花费，和从i-2个台阶出发跳2个台阶的花费。第i-1个台阶和第i-2个台阶已经分别包含了之前跳到当前这个台阶的花费。

3. dp数组如何初始化

是跳的这个操作才需要花费，因此当处于第1个台阶和第2个台阶时，此时花费为0。因此dp[0] == dp[1] == 0

4. 确定遍历顺序

从前向后遍历更新dp数组。

5. 举例推导dp数组

print递推后dp数组

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