动态规划例题_给定模式grammer和文本grameer,写出动态规划

动态规划

这里我们引用一下维基百科的描述：“动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”
通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。
同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。
在一些情况下，动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录的意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的，即先解决子问题，再解决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索到同一个子问题则进行状态记录，防止重复计算。如果题目需求的是最终状态，那么使用动态搜索比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。

一维(空间复杂度有时可压缩到常数)

三步问题

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

输入：n = 3
输出：4
说明: 有四种走法

示例2:

输入：n = 5
输出：13

def waysToStep(self, n: int) -> int:
    if n<=2:
        return n
    a=1
    b=1
    c=2
    d=4
    for i in range(n-3):
        a=b
        b=c
        c=d
        d=(a+b+c)%1000000007
    return d
1
2
3
4
5
6
7
8
9
10
11
12
13

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

def rob(self, nums: List[int]) -> int:
        if len(nums)==1: return nums[0]
        p,q=nums[0],max(nums[1],nums[0])
        l=len(nums)
        for i in range(2,l):
            r=max(nums[i]+p,q)
            p=q
            q=r
        return q
1
2
3
4
5
6
7
8
9

等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        l=len(nums)
        p,q,s=0,0,0
        if l<3:return 0
        for i in range(2,l):
            if nums[i-2]-nums[i-1]==nums[i-1]-nums[i]:
                q=p+1
                s+=q
                p=q
            else:
                p=0
                
        return s
1
2
3
4
5
6
7
8
9
10
11
12
13

二维（空间复杂度有时可压缩到一维）

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

def minPathSum(self, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        for i in range(m):
            for j in range(n):
                if i==0 and j>0:
                    grid[i][j]+=grid[i][j-1]
                elif j==0 and i>0:
                    grid[i][j]+=grid[i-1][j]
                elif i>0 and j>0:
                    grid[i][j]+=min(grid[i][j-1],grid[i-1][j])
                print (grid[i][j])
        return grid[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12

01矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

def updateMatrix(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: List[List[int]]
        """
        n,m=len(mat),len(mat[0])
        a=[[10000 for i in range(0,m)] for j in range(0,n)]
        for i in range(0,n):
            for j in range(0,m):
                if mat[i][j]!=0 :
                    if j>0:
                        a[i][j]=min(a[i][j-1]+1,a[i][j])
                    if i>0:
                        a[i][j]=min(a[i-1][j]+1,a[i][j])
                else:
                    a[i][j]=0
        for i in range(n-1,-1,-1):
            for j in range(m-1,-1,-1):
                if mat[i][j]!=0:
                    if j<m-1:
                        a[i][j]=min(a[i][j],a[i][j+1]+1)
                    if i<n-1:
                        a[i][j]=min(a[i][j],a[i+1][j]+1)
                    
        return a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

分割类型题

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

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

解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
1
2
3
4

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = “12”

输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：

输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：

输入：s = “0”
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

def numDecodings(self, s: str) -> int:
        if s[0]=='0':return 0
        l=len(s)
        dp=[1]*l
        for i in range(1,l):
            if s[i]=='0' and (s[i-1]=='0' or int(s[i-1])>2):
                return 0
            if s[i]=='0' and (s[i-1]=='1' or s[i-1]=='2'):
                 dp[i]=dp[i-2]
            elif int(s[i-1:i+1])<=26 and int(s[i-1:i+1])>=10:
                dp[i]=dp[i-1]+dp[i-2]
            else:
                dp[i]=dp[i-1]
        return dp[len(s)-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

子序列问题

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

def lengthOfLIS(self, nums: List[int]) -> int:
        # l=len(nums)
        # dp=[1]*l
        # for i in range(1,l):
        #     for j in range(0,i):
        #         if nums[i]>nums[j]:
        #             dp[i]=max(dp[i],dp[j]+1)
        # return max(dp)
        dp=[nums[0]]
        for i in nums[1:]:
            if dp[-1]<i:dp.append(i)
            else:
                for j in range(0,len(dp)):
                    if dp[j]>=i:
                        dp[j]=i
                        break
        return len(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    l,m=len(text1),len(text2)
    dp=[[0 for i in range(0,l)] for j in range(0,m)]

    for i in range(0,l):
        if text1[i]==text2[0]:
            for j in range(i,l):
                dp[0][j]=1
            break

    for i in range(0,m):
        if text1[0]==text2[i]:
            for j in range(i,m):
                dp[j][0]=1
            break

    for j in range(1,m):
        for i in range(1,l):
            if text1[i]==text2[j]:
                dp[j][i]=dp[j-1][i-1]+1
            else:
                dp[j][i]=max(dp[j-1][i],dp[j][i-1])


    return dp[m-1][l-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

def wiggleMaxLength(self, nums: List[int]) -> int:
    n = len(nums)
    if n<2:return n
    up = [1]* (n)
    down = [1]* (n)
    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            up[i] = max(up[i - 1], down[i - 1] + 1)
            down[i] = down[i - 1]
        elif nums[i] < nums[i - 1]:
            up[i] = up[i - 1]
            down[i] = max(up[i - 1] + 1, down[i - 1])
        else:
            up[i] = up[i - 1]
            down[i] = down[i - 1]
    return max(up[n - 1], down[n - 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

背包问题

背包问题是一种组合优化的 NP 完全问题：有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
	vector<int> dp(W + 1, 0);
	for (int i = 1; i <= N; ++i) {
		int w = weights[i-1], v = values[i-1];
		for (int j = W; j >= w; --j) {
			dp[j] = max(dp[j], dp[j-w] + v);
		}
	}
	return dp[W];
}
1
2
3
4
5
6
7
8
9
10

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

def canPartition(self, nums: List[int]) -> bool:
    s=sum(nums)
    if s%2==1:return False
    n,m=len(nums),s//2
    dp=[[False for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=True
    for i in range(1,n+1):
        for j in range(1,m+1):
            if j>=nums[i-1]:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp=[[0 for i in range(n+1)] for j in range(m+1)]
        for s in strs:
            for i in range(m,s.count('0')-1,-1):
                for j in range(n,s.count('1')-1,-1):
                    dp[i][j]=max(dp[i][j],dp[i-s.count('0')][j-s.count('1')]+1)
        return dp[m][n]
1
2
3
4
5
6
7

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]

[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]
[0, 1, 2, 3]

[0, 1, 1, 1]
[1, 2, 2, 2]
[1, 2, 3, 3]
[1, 2, 3, 3]
[1, 2, 3, 3]
[1, 2, 3, 4]

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0:return 0
        dp=[amount+2 for i in range(0,amount+1)]
        dp[0]=0
        for i in range(1,amount+1):
            for j in coins:
                if i>=j:
                    dp[i]=min(dp[i-j]+1,dp[i])
        return -1 if (dp[amount]==amount+2) else dp[amount]
1
2
3
4
5
6
7
8
9

字符串编辑

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

def minDistance(self, word1: str, word2: str) -> int:
    l,m=len(word1),len(word2)
    dp=[[0 for i in range(0,l+1)] for j in range(0,m+1)]

    for i in range(0,l+1):
        dp[0][i]=i

    for i in range(0,m+1):
        dp[i][0]=i

    for j in range(1,m+1):
        for i in range(1,l+1):
            if word1[i-1]==word2[j-1]:
                dp[j][i]=min(dp[j-1][i-1],dp[j][i-1]+1,dp[j-1][i]+1)
            else:
                dp[j][i]=min(dp[j-1][i-1],dp[j][i-1],dp[j-1][i])+1


    return dp[m][l]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

只有两个键的键盘

最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

示例 1：

输入：3
输出：3
解释：
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。

示例 2：

输入：n = 1
输出：0

def minSteps(self, n: int) -> int:
    dp=[0 for i in range(0,n+1)]
    h=int(n**0.5)
    for i in range(2,n+1):
        dp[i]=i
        #如果可以整除，则1变成(i//j)的次数=j变成i的次数，所以1变成i的词数=1变成j的次数+j变成i的次数
        for j in range(2,h+1):
            if i%j==0:
                dp[i]=dp[j]+dp[i//j]
    return dp[n]
1
2
3
4
5
6
7
8
9
10

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

示例 2:

输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：

输入：s = “ab”, p = “."
输出：true
解释：".” 表示可匹配零个或多个（’*’）任意字符（’.’）。

def isMatch(self, s: str, p: str) -> bool:
    l,m=len(s),len(p)
    dp=[[False for i in range(l+1)] for j in range(m+1)]
    dp[0][0]=True
    for i in range(1,m+1):
        if p[i-1] == '*':
            dp[i][0] = dp[i-2][0]
    for j in range(1,m+1):
        for i in range(1,l+1):
            if p[j-1]=='.' : 
                dp[j][i]=dp[j-1][i-1]
            elif p[j-1]!="*":
                dp[j][i]=p[j-1]==s[i-1] and dp[j-1][i-1]
            elif p[j-2]!='.' and p[j-2]!=s[i-1]: 
                dp[j][i]=dp[j-2][i]
            else:
                dp[j][i]=dp[j-1][i] or dp[j][i-1] or dp[j-2][i]
    return dp[m][l]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

股票交易

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]

输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

def maxProfit(self, prices: List[int]) -> int:
    if len(prices)==1:return 0
    l=prices[0]
    h=0
    for i in range(1,len(prices)):
        if l>prices[i]:
            l=prices[i]
        else:
            h=max(h,prices[i]-l)
    return h
1
2
3
4
5
6
7
8
9
10

买卖股票的最佳时机Ⅳ

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

def maxProfit(self, k: int, prices: List[int]) -> int:
    l=len(prices)
    if l<2:return 0
    m=0
    if k>=l:
        for i in range(1,l):
            if prices[i]>prices[i-1]:
                m+=prices[i]-prices[i-1]
        return m
    else:
        buy=[-sys.maxsize-1 for i in range(k+1)]
        sell=[0 for i in range(k+1)]
        for i in range(0,l):
            for j in range(1,k+1):
                buy[j]=max(buy[j],sell[j-1]-prices[i])
                sell[j]=max(sell[j],buy[j]+prices[i])
        return sell[k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17