前言

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.不同的二叉搜索树

在这里插入图片描述


总结

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部