⼒扣刷题-python-动态规划-1（动态规划、01背包问题、完全背包问题）⽂章⽬录
1.动态规划
动态规划 是由前⼀个状态推导出
贪⼼算法 是直接取局部最优
动态规划需要直到状态转移公式
解题过程分为5步
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
2.简单和中等题
其实也不⽤写dp数组，这道题就可以解出来，但是这道题还是⽤了动态规划的思想，每个数之间是有关系的这道题同上⼀道题
进阶版的爬楼梯class Solution:    def fib (self, n: int ) -> int:        if  n <2:return n        a, b = 0, 1        for  i  in  range (n-1):              a =a+b              a,b =b,a        return  b
1
2
3
4
5
6
7
8class Solution:    def climbStairs (self, n: int ) -> int:        #每次爬台阶相当于是 n-1情况 和n-2情况和，        dp =[]        for  i  in  range (n ):              if  i <2: dp.append (i+1)              else:                  dp [0]+=dp [1]                  dp [0],dp [1]=dp [1],dp [0]        return  dp [-1]
1
2
3
4
5
6
7
8
9
10
这道题和爬楼梯类似，不过是⼀个⼆维的
这道题的确不好想，⽽且 是个⼆维的循环，以后在动态规划，可能会经常⽤到。class Solution:    def minCostClimbingStairs (self, cost: List [int ]) -> int:        #dp[i]为某⼀层花费  dp[i] =min(dp[i-1] dp[i-2])+cost[i]        #dp[0]=1 dp[1]=100        dp = [0]*len (cost )  #提前配置好空间，再赋值会快很多        for  i  in  range (len (cost )):            if  i <2: dp [i ]=cost [i ]            else:dp [i ]= min (dp [i-1],dp [i-2]) + cost [i ]        return  min (dp [-2:])
1
2
3
4
5
6
7
8
9
10class Solution:    def uniquePaths (self, m: int, n: int ) -> int:        #第mn ⾏肯定是 第m-1 n ⾏ 和第m n-1⾏移动过来的        #dp 表⽰mn 位置的条数 dp[m][n]        #初始化 m=0位置为1 n=0位置为1 因为边上只有⼀条路径可以⾛        dp = [[1]*n for  _ in  range (m )]        for  i  in  range (1,m ):            for  j  in  range (1,n ):                dp [i ][j ]=dp [i-1][j ] + dp [i ][j-1]        return  dp [-1][-1]
1
2
3
4
5
6
7
8
9
10class Solution:    def uniquePathsWithObstacles (self, obstacleGrid: List [List [int ]]) -> int:        #同前⼀道题，但是加⼊了障碍物，所以要将障碍物位置变为0，        dp =  obstacleGrid        for  i  in  range (len (dp )):            for  j  in  range (len (dp [0])):                if  not dp [i ][j ]-1: dp [i ][j ]=0                elif  not i and not j :dp [i ][j ]=1                else: dp [i ][j ] =(dp [i-1][j ] if  i >0 else  0)+(dp [i ][j-1] if  j >0 else  0)        return  dp [-1][-1]
1
2
3
4
5
6
7
8
910class Solution:    def integerBreak (self, n: int ) -> int:        #第n 个 相当于 第n 分解成 n-i 和i 乘积 和dpn-i 和i 乘积⽐较 选最⼤的        #虽然n 是从2开始的 相当于只有n-2+1 个 但是为了遍历⽅便扩充成n 个        dp = [_+1 for  _ in  range (n )]        for  i  in  range (n ):            for  j  in  range (1,i ):                dp [i ] = max (dp [i ] , max (dp [i-j ]*j,(i-j )*j ))        #print(dp)        return  dp [-1] if  n >=4 else  n-1
1
2
3
4
5
6
7
8
9
10
3.01背包问题基础class Solution:    def numTrees (self, n: int ) -> int:        #dp 为n 情况下⼆叉搜索树的个数        #dp[i] +=dp[i-j-1]dp[j] for j in range(i)        dp = [0]*(n+1)                for  i  in  range (n+1):            if  i < 2: dp [i ]=1            else:                for  j  in  range (i ):dp [i ] +=dp [i-j-1]*dp [j ]        #print(dp)          return  dp [-1]
1
2
3
4
5
6
7
8
python 定义数组9
10
11
12
1.01背包基础
背包问题是个啥，我⼀直很好奇，今天终于看到这⾥了，先看下基础理论。# -*- coding: gbk -*-#暴⼒解法nmax =3nlist =[15,20,30]nweigt =[1,3,4]res = []def backtracking (n,weight,hw ):    if  not n - nmax :return res.append (hw )    for  i  in  [0,1]:      if  i:  #选择          hw += nlist [n-1]          weight-=nweigt [n-1]        backtracking (n+1,weight,hw ) backtracking (1,4,0)print ('所有可能的情况为：',res )print ('可以放⼊最⼤为：',max (res ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
暴⼒解法肯定是不可取的，⽤的时间为o（2^n)当这个物体n特别多的时候，这样就太浪费时间了，肯定暴⼒的⽅法是不可取的2.01背包问题的动态规划（⼆维数组）
1）定义
2）递推关系
如果某⼀⾏ 即某⼀个物品i 在j⼩于weight[i]时候，直接取 dp[i-1][j]
如果⼤于weight[i]时候，就可以⽐较他放⼊与不放⼊的总重量的⼤⼩，肯定选最⼤的那个
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
3）初始化
全部初始化为0，但是每次都是和i-1⽐较，所以要初始化i=0⾏
4）遍历顺序
选择⼀⾏⼀⾏遍历，就是⼀个物品⼀个物品来
5）对⽐dp数组并修改程序