day38-39| 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 62.不同路径 343. 整数拆分 96.不同的二叉搜索树

前言

70题拓展和最后两道题没做

动态规划理论基础

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的
动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

此外，需要学会打印中间过程，知道是哪里有问题了；

509. 斐波那契数

本题中for的range应该到n+1，n不是下标，因为f也是从0开始的；

思路

这个是动规的入门题目，因为初始化和递推公式都给出了已经
动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2. 确定递推公式：dp[i] = dp[i-2]+dp[i-1]
3. dp数组如何初始化：题目中把如何初始化也直接给我们了，dp[0] = 0; dp[1] = 1;
4. 确定遍历顺序：dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5. 举例推导dp数组
   按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

方法一 完整动态规划

本题中for的range应该到n+1，n不是下标，因为f也是从0开始的；
下面是自己写的，有点乱七八糟。

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n == 0: return 0if n == 1: return 1dp = [0] * ndp[0] = 0dp[1] = 1for i in range(2,n):dp[i] = dp[i-1]+dp[i-2]# sum_re += dp[i]print(dp)return dp[-1]+dp[-2]

方法二 dp简化版

因为只需要返回fn，所以不需要维护整个list，只需要维护dp[i-2]和dp[i-1]即可；

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n<=1: return n dp = [0, 1]for i in range(2,n+1):sum_ = dp[0] + dp[1]dp[0] = dp[1]dp[1] = sum_return dp[1]

方法三 使用递归

class Solution:def fib(self, n: int) -> int:if n < 2:return nreturn self.fib(n - 1) + self.fib(n - 2)

70. 爬楼梯

由于题目中说了是正整数，所以初始化可以从1开始，不用去想dp[0] 是1还是0

思路

🎈总体思路：（这个我没有想到）
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
这个题目里面的动态规划其实是n情况不同的时候之间的关系，n-1的情况再迈一步和n-2的情况再迈2步都可以到n；
动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：爬到第i层楼梯，有dp[i]种方法
2. 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2] 。
3. dp数组如何初始化：题目说了n>=1，所以从1开始初始化
4. 确定遍历顺序：从前往后
5. 举例推导dp数组

方法一 动态规划

我自己写的如下，但是主要学习教程里面的

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""dp = [0]*nif n <=2: return n dp[0],dp[1] = 1, 2for i in range(2,n):dp[i] = dp[i-1] + dp[i-2]return dp[-1]

方法一2 教程里面的简化方法

1. 不像我用index0当作n==1的时候的种类数，教程里面是一共长n+1，index为0的就让它为0，无视它
2. 简化版本可以只使用3个变量

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n <= 2:return ndp = [0]*(n+1)dp[0], dp[1], dp[2] = 0, 1, 2for i in range(3, n+1):dp[i] = dp[i-1]+dp[i-2]return dp[n]

方法二 拓展

link
如果一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。

#只维护三个变量
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n<=2: return npre1, pre2 = 1, 2for i in range(3,n+1):sum_ = pre1 + pre2pre1 = pre2pre2 = sum_return sum_ class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n<=2: return ndp = [1, 2]for i in range(3,n+1):sum_ = dp[0] + dp[1]dp[0] = dp[1]dp[1] = sum_return sum_ 

746. 使用最小花费爬楼梯

本题中的花费其实理解成体力
题意很清晰，也就是在0或者1台阶的时候都没有花费，只有往上跳了才会花费；例如直接从1开始，那么1是不花费的，但是如果从0开始要往上跳到1，就是花费了10；
最后是要跳上len(cost)的，也就是index为len(cost)，那么总长度就一定是len(cost)+1

思路

动态规划五部曲：
总体思路：dp[i]表示到第i个台阶的最小花费，那么dp[i]就由dp[i-1]跳一步或者dp[i-2]跳两步得到，那么就可以得到递推公式了

1. 💕确定dp数组（dp table）以及下标的含义：到达第i台阶所花费的最少体力为dp[i]。
2. ✨确定递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. dp数组如何初始化： 本题初始化方便了一些，到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。所以初始化 dp[0] = 0，dp[1] = 0;
4. 确定遍历顺序：从前往后
5. 举例推导dp数组

方法一

自己写的易错点： 注意必须要将dp的长度设置为len(cost)+1, 因为其实是到len(cost)的下标

class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""dp = [0] * (len(cost)+1)# dp[0], dp[1] = 0, 0for i in range(2,len(cost)+1):dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])return dp[-1]#简化版本class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""pre0, pre1 = 0, 0 for i in range(2,len(cost)+1):dpi = min(pre0+cost[i-2],pre1+cost[i-1])pre0 = pre1pre1 = dpireturn dpi

方法二 拓展

62.不同路径

图论的深度优先或者广度优先搜索是不行的，会超时，本题优先使用动态规划

思路 动态规划

总体思路：本题我自己想出了和教程一样的思路，也就是第i，j位置的路径数等于它左边格子和上边格子路径数之和
动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2. 确定递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3. dp数组如何初始化🎈：最上面一行和最左边一行的一定是1【本题唯一需要注意的地方】
4. 确定遍历顺序：因为是由左边或者上边的路径数推导出来的，所以从左往后，从上到下
5. 举例推导dp数组

方法一

自己写的注意点

1. ✨定义二维数组的方法：dp = [[0] * n for _ in range(m)]
2. 注意区分行和列：m是行数，也是dp[i][j]中的i，n是j

此外，还可以减少空间复杂度：使用滚动一维数组，即，一行一行走dp[i]（当前要求的路径数）=dp[i-1]（左边的路径数）+dp[i]（上边的路径数）

class Solution(object):def uniquePaths(self, m, n):""":type m: int:type n: int:rtype: int"""dp = [[0] * n for _ in range(m)]dp[0] = [1] * nfor i in range(m):dp[i][0] = 1print(dp)for j in range(1, n):for i in range(1, m):dp[i][j] = dp[i-1][j] + dp[i][j-1]return(dp[-1][-1])# 使用滚动数组class Solution:def uniquePaths(self, m: int, n: int) -> int:# 创建一个一维列表用于存储每列的唯一路径数dp = [1] * n# 计算每个单元格的唯一路径数for j in range(1, m):for i in range(1, n):dp[i] += dp[i - 1]# 返回右下角单元格的唯一路径数return dp[n - 1]

方法二 递归

会超时==
注意截止条件为m1 or n1，表示第一行或者第一列

class Solution(object):def uniquePaths(self, m, n):""":type m: int:type n: int:rtype: int"""if m == 1 or n == 1:return 1return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)

63. 不同路径 II

思路

关键思路：本题与上一条差不多，主要区别在于初始化😢🎶❤️（我一开始思考的时候没有算进来这个），如果障碍物在第一行或者第一列，那么障碍物后面的一定为0
动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：同上一题
2. 确定递推公式：只有当obs里面显示不为1的时候【没有障碍物】，才需要进行递推
3. dp数组如何初始化：因为从*(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1*，dp[0][j]也同理。但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
4. 确定遍历顺序：同上
5. 举例推导dp数组

方法一 动态规划

自己写的

class Solution(object):def uniquePathsWithObstacles(self, obstacleGrid):""":type obstacleGrid: List[List[int]]:rtype: int"""m, n = len(obstacleGrid),len(obstacleGrid[0])#mxndp = [[0]*n for _ in range(m)]#用于记录到ij位置的路径数#初始化for i in range(m):if obstacleGrid[i][0] == 1:breakdp[i][0] = 1for j in range(n):if obstacleGrid[0][j] == 1:breakdp[0][j] = 1print(dp)for i in range(1,m):for j in range(1,n):if obstacleGrid[i][j] != 1:dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[-1][-1]

方法一2 优化教程

1. 教程里面初始化的方法是，后面一个跟前面一个一样，起点为1，后面不出意外都是跟着为1，出了意外就是以它为起始点都是0；
   
2. 进一步优化：使用一维数组，和上面一题的优化方法一样，一行一行的做dp[i]（当前要求的路径数）=dp[i-1]（左边的路径数）+dp[i]（上边的路径数）
   • 下面这一段代码是教程写的很优秀（版本三）：先dp初始化第一行；第二行列的index从0开始，当前位置没有障碍，就开始递推且注意index=0的时候，不递推（注意if的判断）

 # 初始化第一行的路径数for j in range(len(dp)):if obstacleGrid[0][j] == 1:dp[j] = 0elif j == 0:dp[j] = 1else:dp[j] = dp[j - 1]# 计算其他行的路径数for i in range(1, len(obstacleGrid)):for j in range(len(dp)):if obstacleGrid[i][j] == 1:dp[j] = 0elif j != 0:dp[j] = dp[j] + dp[j - 1]

343. 整数拆分

96.不同的二叉搜索树

总结