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 0
        if n == 1: return 1
        dp = [0] * n
        dp[0] = 0
        dp[1] = 1
        for 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 n
        return 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]*n
        if n <=2: return n 
        dp[0],dp[1] = 1, 2
        for 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 n
        dp = [0]*(n+1)
        dp[0], dp[1], dp[2] = 0, 1, 2
        for 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 n
        pre1, pre2 = 1, 2
        for i in range(3,n+1):
            sum_ = pre1 + pre2
            pre1 = pre2
            pre2 = sum_
        return sum_ 
        
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=2: return n
        dp = [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, 0
        for 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 = pre1
            pre1 = dpi
        return 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] * n
        for i in range(m):
            dp[i][0] = 1
        print(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 1
        return 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])#mxn
        dp = [[0]*n for _ in range(m)]#用于记录到ij位置的路径数
        #初始化
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1
        print(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] = 0
     elif j == 0:
         dp[j] = 1
     else:
         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] = 0
         elif j != 0:
             dp[j] = dp[j] + dp[j - 1]

343. 整数拆分

96.不同的二叉搜索树

总结