动态规划

详细总结所有动态规划面试题
跟着刷完你就会！

动态规划思路：

采用动态五部曲

1. 一维动态规划–简单dp：

斐波那契数

​

1. dp数组的含义，dp[i]=F(i)的值
2. 递推方程 dp[i]=dp[i-1]+dp[i-2]
3. dp的初始化，dp[0]=0,dp[1]=1
4. 从前到后遍历

def fib(self, n):
    dp=[0,1]
    if n<2:
        return dp[n]
    for i in range(2,n+1):
        dp.append(dp[i-1]+dp[i-2])
    return dp[-1] 
1
2
3
4
5
6
7

我们发现只用到前两个状态的数值，可以只用两个变量存储, 空间复杂度为O(1)

def fib(self, n):
    dp=[0,1]
    if n<2:
        return dp[n]
    for i in range(2,n+1):
        tmp=dp[0]+dp[1]
        dp[0]=dp[1]
        dp[1]=tmp
    return dp[-1] 
1
2
3
4
5
6
7
8
9

爬楼梯

​

1. dp[i]表示到i阶梯有多少种爬楼梯方法
2. dp[i-1]再跨一步或者dp[i-2]再跨两步就可以到dp[i]=dp[i-1]+dp[i-2]
3. 初始化，dp[0]没有意义，dp[1]=1,dp[2]=2
4. 从前到后遍历

def climbStairs(self, n):
    dp=[0,1,2]
    if n<3:
        return dp[n]
    for i in range(3,n+1):
        dp.append(dp[i-1]+dp[i-2])
    return dp[-1]
1
2
3
4
5
6
7

同样可以用两个变量降低一下空间复杂度

使用最小花费爬楼梯

​

1. 到达第下标为i的台阶花费的最少体力dp[i]
2. dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
3. 初始化，dp[0]=cost[0],dp[1]=cost[1]
4. 从前往后遍历,原数组：[1,100,1,1,1,100,1,1,100,1] dp数组：[1, 100, 2, 3, 3, 103, 4, 5, 104, 6]
5. 因此最后要取dp[-1]和dp[-2]的最小值，因为这两个最后一步可以直达并且不花费

def minCostClimbingStairs(self, cost):
    dp=[cost[0],cost[1]]
    n=len(cost)
    for i in range(2,n):
        dp.append(min(dp[i-1],dp[i-2])+cost[i])
    return min(dp[-1],dp[-2])
1
2
3
4
5
6

粉刷房子

​

def minCost(self, costs: List[List[int]]) -> int:
    #dp[i][j]，j取0-2，表示第i间房子粉刷成三种颜色的最小花费
    #初始化，dp[0][0-2]=costs[0][0-2]
    #dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0]
    #滚动数组覆盖
    dp=costs[0].copy()
    for i in range(1,len(costs)):
        tmp=dp.copy()
        dp[0]=min(tmp[1],tmp[2])+costs[i][0]
        dp[1]=min(tmp[0],tmp[2])+costs[i][1]
        dp[2]=min(tmp[0],tmp[1])+costs[i][2]
    return min(dp)
1
2
3
4
5
6
7
8
9
10
11
12

字符串反转

​

dp[i][0]=dp[i-1][0]+(s[i]==0? 0:1)

dp[i][1]=min(dp[i-1][0]+dp[i-1][1])+(s[i]==1?0:1)

dp[0]=[(s[0]==0?0:1),(s[1]==1?0:1)]

def minFlipsMonoIncr(self, s: str) -> int:
    dp=[0 if s[0]=="0" else 1,0 if s[0]=="1" else 1]
    for i in range(1,len(s)):
        tmp=dp.copy()
        dp[0]=tmp[0]+(0 if s[i]=="0" else 1)
        dp[1]=min(tmp[0],tmp[1])+(0 if s[i]=="1" else 1)
    return min(dp)
1
2
3
4
5
6
7

不同路径

​

机器⼈从(0 , 0) 位置触发，到(m - 1, n - 1)终点

1. dp数组的含义是表示走到dp[i][j]位置的路径数量
2. dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，只能从这两个方向过来
3. dp[i][0]和dp[0][j]都是1，初始化，因为到这的路径只有1条
4. 遍历从左到右，从上到下

def uniquePaths(self, m, n):
    dp=[[0]*n for _ in range(m)]
    for i in range(m):
        dp[i][0]=1
    for i in range(n):
        dp[0][i]=1
    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
10

不同路径-有障碍物

​

1. dp数组的含义依然是表示走到当前位置的路径dp[i][j]
2. 但是如果位置不是障碍，才去推导dp[i][j]=dp[i][j-1]+dp[i-1][j], else=0
3. 初始化和上面一样，但是要排除有障碍的情况，有障碍的后面就不初始化，因为无法到达，需要上行
4. 遍历依然从上到下，从左到右

def uniquePathsWithObstacles(self, obstacleGrid):
    m=len(obstacleGrid)
    n=len(obstacleGrid[0])
    dp=[[0]*n for _ in range(m)]
    for i in range(m):
        if obstacleGrid[i][0]==1:
            break
        dp[i][0]=1
    for i in range(n):
        if obstacleGrid[0][i]==1:
            break
        dp[0][i]=1
    for i in range(1,m):
        for j in range(1,n):
            if obstacleGrid[i][j]==0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            else:
                dp[i][j]=0
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

整数拆分

​

1. dp表示的的含义：拆分i，dp[i]表示拆分出的最大值
2. dp[i]=max(dp[i],j*(i-j),j*dp[i-j]),j从1开始遍历，到j-1,要比较dp[i]的原因是dp[i]是循环保存的之前最大值
3. 初始化dp[2]=1，dp[1]=0
4. 遍历，i从3开始，j从1开始,正好用dp[2]的值，也用到了dp[1]的值但是并没有用，因为是0

def integerBreak(self, n):
    dp=[0]*(n+1)
    dp[2]=1
    for i in range(3,n+1):
        for j in range(1,i):
            dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
    return dp[-1]
1
2
3
4
5
6
7

不同的二叉搜索树

​

​

1. 分析dp[i]表示的是i个节点组成的二叉搜索树的种类
2. dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量，j从1开始遍历，遍历到i
3. 如上图的递推关系，我们发现以j为头节点，j-1左子树，i-j个右子树
4. dp[0]=1，即左子树为空
5. 遍历，i从1-n，j从1-i

def numTrees(self, n):
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        for j in range(1,i+1):
            dp[i]+=dp[j-1]*dp[i-j]
    return dp[-1]
1
2
3
4
5
6
7

2. 复杂动态规划–0-1背包问题：

​

0-1背包问题：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

1. 确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

1. 确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

**不放物品i：**由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)

**放物品i：**由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

1. 初始化：即dp[i][0]=0，没有疑问，因为背包容量为0的时候就没有任何价值

在看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

#初始化
weight=[1,3,4]
value=[15,20,30]
w=len(weight)
n=4
dp=[[0]*(n+1) for _ in range(w)]
for j in range(n+1):
    if j<weight[0]:
        dp[0][j]=0
    else:
        dp[0][j]=value[0]
1
2
3
4
5
6
7
8
9
10
11

1. 遍历顺序：

先遍历物品，后遍历背包重量

物品i从1- >w，j->bagweight

for i in range(1,w):
    for j in range(0,n+1):
        if j<weight[i]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
print(dp)
1
2
3
4
5
6
7

压缩0-1背包问题：

dp[i][j]只与dp[i-1]这一层的j有关，因此可以节省空间

1. 确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。用循环表示拿到哪件商品了

1. 递推，等于把i层的东西去掉了，递推方程为

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
1

1. 初始化，因为dp[j]表示容量为j的背包，因此dp[0]=0,其余位置也初始化为0
2. 二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么前面的物品0就会被重复加入多次！在max的前提下

weight=[1,3,4]
value=[15,20,30]
w=len(weight)
n=4
dp=[0]*(n+1)
for i in range(0,w):
    for j in range(n,weight[i]-1,-1): #必须倒序，才能用到上一层的前面的值，不然会反复加
       dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp)
1
2
3
4
5
6
7
8
9

分割等和子集：

​

1. 这里首先将其套到背包问题，背包容量为sum/2，weight=nums，value=nums
2. 即dp[j]表示容量为j的背包，当前放入i件物品之后容纳的最大价值
3. 递推方程：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]),这里的i表示拿到了第几个数
4. 初始化，dp[0]=0,一个数字不放
5. 遍历顺序：i从0->len(nums),j从sum/2->0

def canPartition(self, nums):
    bag_sum=sum(nums)
    if bag_sum%2==1:
        return False
    bag_sum=bag_sum/2
    dp=[0]*(bag_sum+1)
    for i in range(len(nums)):
        for j in range(bag_sum,-1,-1):
            if j>=nums[i]:
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
    return True if dp[bag_sum]==bag_sum else False
1
2
3
4
5
6
7
8
9
10
11

最后一块石头重量：

​

1. 抽象到01背包问题，可以理解成，分出重量最多的两堆石头，即分出最高为一半重量的石头堆
2. dp[j]表示重量为j的背包，在当前i之前放入后所能容纳的最大价值
3. 递推方程：dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])
4. 初始化dp[0]=0，长度为weight/2
5. 遍历顺序i从0->len（stones），j从weight/2-0
6. 注意，这里我们先向下取整，得到左边这堆的最大重量dp[-1]，右边的是sum-dp[-1]

def lastStoneWeightII(self, stones):
    bag_sum=sum(stones)
    target=bag_sum//2
    dp=[0]*(target+1)
    for i in range(len(stones)):
        for j in range(target,-1,-1):
            if j>=stones[i]:
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])
    return bag_sum-2*dp[-1]
1
2
3
4
5
6
7
8
9

目标和：

​

1. dp[j]表示当前i层所凑够背包j的解法数量，设➕号的和为x，剩下的数字放-号，为sum-x
2. 注意，因为变成了求解法数量了，不是求当前背包j的最大价值了
3. dp[j]+=dp[j-nums[i]]
4. 初始化dp[0]=1，背包为0的解法是1种，即什么也不拿
5. x-（sum-x）=target，x=（target+sum）/2，如果向下取整，奇数无解，排除，abs（S）>sum也无解，因此背包容量为x=（target+sum）/2

def findTargetSumWays(self, nums, target):
    num_sum=sum(nums)
    if (target+num_sum)%2==1 or abs(target)>num_sum:
        return 0
    max_bag=(target+num_sum)//2
    dp=[0]*(max_bag+1)
    dp[0]=1
    for i in range(len(nums)):
        for j in range(max_bag,nums[i] - 1,-1):#这里必须要-1,到0,因为dp[0]！=0
            dp[j]+=dp[j-nums[i]]
    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

一和零：

​

1. 这题本质上是一个两个维度的0-1背包问题，mn表示01的容量限制，子集个数是价值
2. dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
3. dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
4. 初始化，背包容量为m，n，dp[0][0]=0
5. 外层物品(字符串)，内层容量（分别遍历mn，倒序）遍历。

def findMaxForm(self, strs, m, n):
    dp=[[0]*(n+1) for _ in range(m+1)]
    for one_str in strs:
        oneNum = 0
        zeroNum = 0
        for s in one_str:
            if s=='0':
                zeroNum+=1
            else:
                oneNum+=1
        for i in range(m,zeroNum-1,-1):
            for j in range(n,oneNum-1,-1):
                dp[i][j]=max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1)
    return dp[-1][-1]         
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 复杂动态规划–完全背包问题：

完全背包问题：

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

唯一要改的就是遍历的顺序的一个设置，不用倒序遍历，而是要正序！

weight=[1,3,4]
value=[15,20,30]
w=len(weight)
n=4#最大容量
dp=[0]*(n+1)
for i in range(0,w):
    for j in range(weight[i],n+1): #正序
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp)
1
2
3
4
5
6
7
8
9

最少的硬币数目：

​

1. 经典的完全背包问题，每个硬币可以用无限次，背包容量为amount，价值为次数，求最少，dp[j]表示组成j金额的最少硬币数量
2. 递推公式，dp[j]=min(dp[j],dp[j-coins[i]]+1])
3. 初始化，dp[0]=0,dp=[amount+1]*(amount+1)
4. 遍历外圈物品，内圈价值,正序从coins遍历。（完全背包正向遍历）

def coinChange(self, coins, amount):
    dp=[amount+1]*(amount+1)
    dp[0]=0
    for i in range(len(coins)):
        for j in range(coins[i],amount+1):
            dp[j]=min(dp[j],dp[j-coins[i]]+1)
    if dp[-1]==amount+1:#如果依然是初始化的值，说明没法凑成        
        return -1
    else:
        return dp[-1]
1
2
3
4
5
6
7
8
9
10

硬币组合数目：

​

组合排列的数目。

​

组合和排列并不相同。

1. dp的含义，dp[j]表示面值为j的组合数目
2. 递推公式 dp[j] += dp[j - coins[i]];
3. 初始化，dp[0]=1，其余的位置初始化位0就好
4. 这里的遍历方式直接影响最后的结果。因为是无限背包问题，所以需要正序

如果是组合问题：应该先物品，后背包

for i in range(len(coins)):
    for j in range(coins[i],amount+1):
        dp[j]+=dp[j-coins[i]]
1
2
3

如果是排列问题，应该先背包后物品。

for j in range(1,amount+1):
    for i in range(len(coins)):
        if j >=coins[i]:
            dp[j]+=dp[j-coins[i]]
1
2
3
4

因此本题代码：

def change(self, amount, coins):
    dp=[0]*(amount+1)
    dp[0]=1
    for i in range(len(coins)):
        for j in range(coins[i],amount+1):
            dp[j]+=dp[j-coins[i]]
    return dp[-1]
1
2
3
4
5
6
7

组合总和:

​

1. dp[j]: 凑成目标正整数为j的排列个数为dp[j]
2. dp[j] += dp[j - nums[i]];
3. 初始化，dp[0]=1，其余初始化0
4. 排列问题，所以外层遍历背包，内层遍历数字

def combinationSum4(self, nums, target):
    dp=[0]*(target+1)
    dp[0]=1
    for j in range(1,target+1):
        for i in range(len(nums)):
            if j>=nums[i]:
                dp[j]+=dp[j-nums[i]]
    return dp[-1]
1
2
3
4
5
6
7
8

爬楼梯：

​

​

跳的阶数就是物品，楼顶就是amount，跳法就是组合数目，这里我们设置nums为跳的台阶层数

1. dp[j]表示跳的阶梯是j的跳法
2. dp[j]+=dp[j-nums[i]]
3. 初始化，dp[0]=1，其余为0
4. 遍历顺序，因为是排列，先上1和先上2是不一样的，所以先背包放外面,物品放内层

def climbStairs(self, n):
    dp=[0]*(n+1)
    dp[0]=1
    nums=[1,2]
    for j in range(1,n+1):
        for i in range(len(nums)):
            if j>=nums[i]:
                dp[j]+=dp[j-nums[i]]
    return dp[-1]
1
2
3
4
5
6
7
8
9

完全平方数：

​

首先分析，很浓的完全背包问题，因此需要正向遍历，然后是求最小价值，因此递推用min并且不用区分组合还是排列。即先背包还是先物品都可以

背包容量为n，物品为1，4，9.。。。一直到小于n

1. dp[j]表示组成j的最少数量
2. dp[j]=min(dp[j],dp[j-i*i]+1)
3. dp初始化，dp[0]=0,其余的要初始化为n，即为n个1
4. 遍历，先背包还是先物品都可以，然后完全背包问题需要正向
5. i从0->iii到n

def numSquares(self, n):
    dp=[n]*(n+1)
    dp[0]=0
    thinglen=int(pow(n,0.5))
    for i in range(thinglen+1):
        for j in range(i*i,n+1):
            dp[j]=min(dp[j],dp[j-i*i]+1)
    return dp[-1]
1
2
3
4
5
6
7
8

def wordBreak(self, s, wordDict):
    dp=[False]*(len(s)+1)
    dp[0]=True
    for i in range(len(s)):
        for j in range(i+1,len(s)+1):
            if dp[i] and s[i:j] in wordDict:
                dp[j]=True
    return dp[-1]
1
2
3
4
5
6
7
8

def wordBreak(self, s, wordDict):
    dp=[False]*(len(s)+1)
    dp[0]=True
    for j in range(1,len(s)+1):
        for i in range(0,j):
            if dp[i] and s[i:j] in wordDict:
                dp[j]=True
    return dp[-1]
1
2
3
4
5
6
7
8

def rob(self, nums):
    if len(nums)==0:
        return 0
    if len(nums)==1:
        return nums[0]
    dp=[0]*len(nums)
    dp[0]=nums[0]
    dp[1]=max(nums[0],nums[1])
    for i in range(2,len(nums)):
        dp[i]=max(dp[i-2]+nums[i],dp[i-1])
    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

def rob(self, nums):
    def robv1(nums,l,r):
        if r==l:
            return nums[l]
        dp=[0]*(r-l+1)
        dp[0]=nums[l]
        dp[1]=max(nums[l],nums[l+1])
        for i in range(2,r-l+1):
            dp[i]=max(dp[i-2]+nums[l+i],dp[i-1])
        return dp[-1]
    if len(nums)==0:
        return 0
    if len(nums)==1:
        return nums[0]
    result1=robv1(nums,0,len(nums)-2)
    result2=robv1(nums,1,len(nums)-1)
    return max(result1,result2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def rob(self, root):
    def robtree(node):
        if not node:
            return [0,0]
        result1=robtree(node.left)
        result2=robtree(node.right)
        left=max(result1[0],result1[1])+max(result2[0],result2[1])
        right=node.val+result1[0]+result2[0]
        return [left,right]
    result=robtree(root)
    return max(result[0],result[1])
1
2
3
4
5
6
7
8
9
10
11

if not prices:
    return 0
profit=0
cost=prices[0]
for i in range(1,len(prices)):
    cost=min(cost,prices[i])
    profit=max(profit,prices[i]-cost)
return profit
1
2
3
4
5
6
7
8

def maxProfit(self, prices):
    if not prices:
        return 0
    dp=[[0,0] for _ in range (len(prices))]
    dp[0][0]=-prices[0]
    dp[0][1]=0
    for i in range(1,len(prices)):
        dp[i][0]=max(dp[i-1][0],-prices[i])
        dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]) 
    return dp[-1][1]
1
2
3
4
5
6
7
8
9
10

def maxProfit(self, prices):
    #等价于每天都在买卖
    profit = 0
    for i in range(1, len(prices)):
        tmp = prices[i] - prices[i - 1]
        if tmp > 0: 
            profit += tmp
    return profit
1
2
3
4
5
6
7
8

def maxProfit(self, prices):
    if not prices:
        return 0
    dp=[[0,0] for _ in range (len(prices))]
    dp[0][0]=-prices[0]
    dp[0][1]=0
    for i in range(1,len(prices)):
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
        dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]) 
    return dp[-1][1]
1
2
3
4
5
6
7
8
9
10

def maxProfit(self, prices):
    if not prices:
        return 0
    dp=[[0,0,0,0,0] for _ in range (len(prices))]
    dp[0][1]=-prices[0]
    dp[0][3]=-prices[0]
    for i in range(1,len(prices)):
        dp[i][0]=dp[i-1][0]
        dp[i][1]=max(dp[i-1][1],-prices[i]+dp[i-1][0]) 
        dp[i][2]=max(dp[i-1][2],prices[i]+dp[i-1][1]) 
        dp[i][3]=max(dp[i-1][3],-prices[i]+dp[i-1][2]) 
        dp[i][4]=max(dp[i-1][4],prices[i]+dp[i-1][3])   
    return dp[-1][4]
1
2
3
4
5
6
7
8
9
10
11
12
13

def maxProfit(self, k, prices):
    if not prices:
        return 0
    dp=[[0]*(2*k+1) for _ in range (len(prices))]
    for i in range(2*k+1):
        if i%2==1:
            dp[0][i]=-prices[0]
    for i in range(1,len(prices)):
        dp[i][0]=dp[i-1][0]
        for j in range(1,2*k+1):
            if j%2==1:
                dp[i][j]=max(dp[i-1][j],-prices[i]+dp[i-1][j-1]) 
            else:
                dp[i][j]=max(dp[i-1][j],prices[i]+dp[i-1][j-1])       
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def maxProfit(self, prices, fee):
    #贪心
    #等价于每天都在买卖
    profit = 0
    buy=prices[0]+fee
    for i in range(1, len(prices)):
        if prices[i]+fee<buy:
            buy=prices[i]+fee
        elif prices[i]-buy>0: 
            profit += prices[i]-buy
            buy=prices[i]#这里是因为并不知道现在卖了会是最大收益，因此保存buy，之后循环如果prices直接大于当前buy，那么等于使用后面的价格卖的，pmax-pmin+profit=用最高价卖的
    return profit
1
2
3
4
5
6
7
8
9
10
11
12

def maxProfit(self, prices):
    if not prices:
        return 0
    dp=[[0,0] for _ in range (len(prices))]
    dp[0][0]=-prices[0]
    dp[0][1]=0
    for i in range(1,len(prices)):
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
        dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]-fee) 
    return dp[-1][1]
1
2
3
4
5
6
7
8
9
10

dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i])
dp[i][1]=max(dp[i-1][1],dp[i-1][3])
dp[i][2]=dp[i-1][0]+prices[i]
dp[i][3]=dp[i-1][2]
1
2
3
4

def maxProfit(self, prices):
    if not prices:
        return 0
    dp=[[0,0,0,0] for _ in range (len(prices))]
    dp[0][0]=-prices[0]
    for i in range(1,len(prices)):
        dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i])
        dp[i][1]=max(dp[i-1][1],dp[i-1][3])
        dp[i][2]=dp[i-1][0]+prices[i]
        dp[i][3]=dp[i-1][2]
    return max(dp[-1])
1
2
3
4
5
6
7
8
9
10
11

def lengthOfLIS(self, nums):
    dp=[1]*(len(nums))
    result=1
    for i in range(1,len(nums)):
        for j in range(0,i):
            if nums[i]>nums[j]:
                dp[i]=max(dp[i],dp[j]+1)
        result=max(result,dp[i])
    return result
1
2
3
4
5
6
7
8
9

def findLengthOfLCIS(self, nums):
    dp=[1]*(len(nums))
    for i in range(1,len(nums)):
        if nums[i]>nums[i-1]:
            dp[i]=dp[i-1]+1
    return max(dp)
1
2
3
4
5
6

def findLength(self, nums1, nums2):
    dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
    result=0
    for i in range(1,len(nums1)+1):
        for j in range(1,len(nums2)+1):
            if nums1[i-1]==nums2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            result=max(dp[i][j],result)
    return result
1
2
3
4
5
6
7
8
9

def longestCommonSubsequence(self, text1, text2):
    dp=[[0]*(len(text2)+1) for _ in range(len(text1)+1)]
    for i in range(1,len(text1)+1):
        for j in range(1,len(text2)+1):
            if text1[i-1]==text2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9

dp=[ [""]*(len(text2)+1) for _ in range(len(text1)+1)]
for i in range(1,len(text1)+1):
    for j in range(1,len(text2)+1):
        if text1[i-1]==text2[j-1]:
            dp[i][j]=dp[i-1][j-1]+text2[j-1]
        else:
            if len(dp[i-1][j])>len(dp[i][j-1]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11

def maxUncrossedLines(self, nums1, nums2):
    dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
    for i in range(1,len(nums1)+1):
        for j in range(1,len(nums2)+1):
            if nums1[i-1]==nums2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9

def maxSubArray(self, nums):
    dp=[0]*len(nums)
    dp[0]=nums[0]
    res=nums[0]
    for i in range(1,len(nums)):
        dp[i]=max(nums[i],nums[i]+dp[i-1])
        res=max(dp[i],res)
    return res
1
2
3
4
5
6
7
8

def isSubsequence(self, s, t):
    l=0
    r=0
    while l<len(s) and r<len(t):
        if s[l]==t[r]:
            l+=1
        r+=1
    if l==len(s):
        return True
    else:
        return False
1
2
3
4
5
6
7
8
9
10
11

def isSubsequence(self, s, t):
    dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(1,len(s)+1):
        for j in range(1,len(t)+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=dp[i][j-1]
            
    return dp[-1][-1]==len(s)
1
2
3
4
5
6
7
8
9
10