动态规划

0. 动态规划理论基础

0.1 动态规划理论入门

定义:
动态规划，英文：Dynamic Programming，简称DP。
如果某一问题有很多重叠子问题，使用动态规划是最有效的。

与贪心算法的区别:

  • 动态规划:
    每一个状态一定是由上一个状态推导出来的
  • 贪心算法:
    没有状态推导，从局部直接选最优的

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

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

0.2 动态规划的解题步骤

分为以下五步：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

0.3 题目目录

0.3.1 一维动态规划

0.3.2 二维动态规划

0.3.3 子序列问题

0.3.4 回文串与编辑问题

0.3.5 股票问题

0.3.6 背包问题

0.3.7 前缀和问题

0.3.8 复合问题

1. 一维动态规划

1.1 斐波那契数列

https://leetcode-cn.com/problems/fibonacci-number/

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

提示：

  • 0 <= n <= 30
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        dp = [0]*(n+1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

1.2 泰波那契数列

https://leetcode-cn.com/problems/n-th-tribonacci-number/

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

1
2
3
4
5
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

1
2
输入：n = 25
输出：1389537

提示：

  • 0 <= n <= 37
  • 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1
        dp = [0]*(n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        return dp[n]

1.3 爬楼梯 I

描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：
给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

链接:
https://leetcode-cn.com/problems/climbing-stairs/

解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 2:
            return 1
        if n == 2:
            return 2
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

1.4 爬楼梯 II

描述：

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

1
2
3
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：

1
2
3
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

链接：
https://leetcode-cn.com/problems/min-cost-climbing-stairs/

提示：

  • cost 的长度范围是 [2, 1000]。
  • cost[i] 将会是一个整型数据，范围为 [0, 999] 。

解：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minCostClimbingStairs(self, cost) -> int:
        if len(cost) < 2:
            return cost[-1]
        cost.append(0)
        dp = [0]*(len(cost))
        dp[0] = 0
            
        for i in range(2,len(dp)):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[-1]

1.5 跳跃游戏 I

描述：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] <= 105

链接：
https://leetcode-cn.com/problems/jump-game/

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canJump(self, nums) -> bool:
        dp = [False]*len(nums)
        dp[0] = True
        for i in range(1,len(nums)):
            if dp[i-1] == False:
                dp[i] = False
            elif nums[i-1] == 0:
                for j in range(i-1,-1,-1):
                    if nums[j] >= i - j:
                        dp[i] = True
                        print(j,i)
                        break
            else:
                dp[i] = True
        return dp[-1]

1.6 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

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

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

https://leetcode-cn.com/problems/jump-game-ii/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def jumpByGreedy(self, nums):
        if len(nums) < 2:
            return 0
        p = 0
        q = nums[p]
        if p + q >= len(nums):
            return 1
        counter = 0
        while p + q < len(nums)-1:
            t = 0
            for i in range(p+1,p+q+1):
                if nums[i] + i >= t:
                    t = nums[i] + i
                    p = i
            q = nums[p]
            counter += 1
            if  p + q > len(nums):
                break
        return counter+1
    
    def jumpByDP(self, nums):
        if len(nums) < 2:
            return 0
        dp = list(range(len(nums)))
        dp[0] = 0

        for i in range(1,len(nums)):
            t = nums[i-1] + i-1
            if t >= len(nums) - 1:
                dp[-1] = dp[i-1] + 1
                break
            for j in range(i,t+1):
                dp[j] = min(dp[i-1]+1,dp[j])
        print(dp)
        return dp[-1]

if __name__ == "__main__":
    s = Solution()
    print(s.jumpByDP([10,9,8,7,6,5,4,3,2,1,1,0]))

1.7 打家劫舍I

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

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

示例 1：

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

示例 2：

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

链接：
https://leetcode-cn.com/problems/house-robber/

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

解：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def jumpByGreedy(self, nums):
        if len(nums) < 2:
            return 0
        p = 0
        q = nums[p]
        if p + q >= len(nums):
            return 1
        counter = 0
        while p + q < len(nums)-1:
            t = 0
            for i in range(p+1,p+q+1):
                if nums[i] + i >= t:
                    t = nums[i] + i
                    p = i
            q = nums[p]
            counter += 1
            if  p + q > len(nums):
                break
        return counter+1
    
    def jumpByDP(self, nums):
        if len(nums) < 2:
            return 0
        dp = list(range(len(nums)))
        dp[0] = 0

        for i in range(1,len(nums)):
            t = nums[i-1] + i-1
            if t >= len(nums) - 1:
                dp[-1] = dp[i-1] + 1
                break
            for j in range(i,t+1):
                dp[j] = min(dp[i-1]+1,dp[j])
        print(dp)
        return dp[-1]

if __name__ == "__main__":
    s = Solution()
    print(s.jumpByDP([10,9,8,7,6,5,4,3,2,1,1,0]))

1.8 打家劫舍II

描述：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

示例 1：

1
2
3
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

1
2
3
4
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

链接：
https://leetcode-cn.com/problems/house-robber-ii/

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, nums) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        a1 = self.fdp(nums[1:])
        a2 = self.fdp(nums[:len(nums)-1])
        return max(a1, a2)
    
    def fdp(self, nums):
        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.9 删除并获得点数

https://leetcode-cn.com/problems/delete-and-earn/

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

1
2
3
4
5
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

1
2
3
4
5
6
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104
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
26
27
28
29
30
class Solution:
    def deleteAndEarn(self, nums) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        maxNum = self.getMaxNum(nums)
        numsList = [0]*(maxNum+1)
        for i in nums:
            numsList[i] += 1
        return self.fdp(numsList)
        
    def getMaxNum(self, arr):
        if len(arr) == 0:
            return None
        if len(arr) == 1:
            return arr[0]
        t = arr[0]
        for i in arr:
            if i > t:
                t = i
        return t
    def fdp(self, arr):
        dp = [0]*len(arr)
        dp[0] = 0
        dp[1] = arr[1]
        for i in range(2,len(arr)):
            dp[i] = max(dp[i-1], (dp[i-2]+i * arr[i]))
        return dp[-1]

1.10 最佳观光组合

https://leetcode-cn.com/problems/best-sightseeing-pair/

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例 1：

1
2
3
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

1
2
输入：values = [1,2]
输出：2

提示：

  • 2 <= values.length <= 5 * 104
  • 1 <= values[i] <= 1000

解:
动态规划和贪心算法都可解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# https://leetcode-cn.com/problems/best-sightseeing-pair/
class Solution:
    def maxScoreSightseeingPairByDP(self, values):
        if len(values) == 2:
            return values[0] + values[1] -1
        dp = [0] *len(values)
        dp[0] = values[0]
        maxValue = dp[0]
        for i in range(1,len(values)):
            maxValue = max(maxValue, dp[i-1]+values[i]-i)
            dp[i] = max(dp[i-1],values[i]+i)
        return maxValue
    
    def maxScoreSightseeingPairByGreedy(self, values):
        maxValue = 0
        lastMVPIndex = 0
        for i in range(1,len(values)):
            maxValue = max(maxValue, values[lastMVPIndex]+lastMVPIndex+values[i]-i)
            if values[i] >= values[lastMVPIndex]+lastMVPIndex-i:
                lastMVPIndex = i
        return maxValue

1.11 丑数-II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

1
2
3
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

1
2
3
输入：n = 1
输出：1
解释：1 通常被视为丑数。

链接:
https://leetcode-cn.com/problems/ugly-number-ii/

提示：

  • 1 <= n <= 1690

解：
同剑指-49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def nthUglyNumber(self, n):
        if n == 1:
            return 1
        dp = [0]*n
        dp[0] = 1
        a,b,c = 0,0,0
        for i in range(1,n):
            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
            dp[i] = min(n2,n3,n5)
            if dp[i] == n2:
                a += 1
            if dp[i] == n3:
                b += 1
            if dp[i] == n5:
                c += 1
        return dp[-1]

2. 二维动态规划

2.1 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

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

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

示例 1：

img

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

示例 2：

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

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

解:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for i in range(1, len(grid)):
            grid[i][0] += grid[i-1][0]
        for j in range(1, len(grid[0])):
            grid[0][j] += grid[0][j-1]
        for i in range(1,len(grid)):
            for j in range(1,len(grid[0])):
                grid[i][j] += min(grid[i-1][j],grid[i][j-1])
        return grid[-1][-1]

2.2 下降路径最小和

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。

具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

1
2
3
4
5
6
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]

示例 2：

1
2
3
4
5
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
 [-40,-5]]

示例 3：

1
2
输入：matrix = [[-48]]
输出：-48

**链接:

**https://leetcode-cn.com/problems/minimum-falling-path-sum/

提示：

  • n == matrix.length
  • n == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

解:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minFallingPathSum(self, matrix):
        for i in range(1,len(matrix)):
            for j in range(len(matrix[0])):
                if j == 0:
                    matrix[i][0] += min(matrix[i-1][0],matrix[i-1][1])
                elif j == len(matrix[0])-1:
                    matrix[i][-1] += min(matrix[i-1][-1],matrix[i-1][-2])
                else:
                    matrix[i][j] += min(matrix[i-1][j-1],matrix[i-1][j],matrix[i-1][j+1])
        return min(matrix[-1])

2.3 不同路径 I

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

链接:
https://leetcode-cn.com/problems/unique-paths/

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

解:

1
2
3
4
5
6
7
8
9
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 0 or n == 0:
            return 0
        dp = [[1 for row in range(n)] for col 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]

2.4 不同路径 II

链接:
https://leetcode-cn.com/problems/unique-paths-ii/

描述:
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

img

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

1
2
3
4
5
6
7
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

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

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 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
26
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid) -> int:
        if len(obstacleGrid) == 0:
            return 0
        if obstacleGrid[0][0] == 1:
            return 0
        obstacleGrid[0][0] = 1
        for i in range(1,len(obstacleGrid)):
            if obstacleGrid[i][0] == 1:
                obstacleGrid[i][0] = 0
            else:
                obstacleGrid[i][0] = obstacleGrid[i-1][0]

        for j in range(1,len(obstacleGrid[0])):
            if obstacleGrid[0][j] == 1:
                obstacleGrid[0][j] = 0
            else:
                obstacleGrid[0][j] = obstacleGrid[0][j-1]

        for i in range(1,len(obstacleGrid)):
            for j in range(1,len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
        return obstacleGrid[-1][-1]

2.5 杨辉三角

https://leetcode-cn.com/problems/pascals-triangle/

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1:

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

1
2
输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def generate(self, numRows):
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]
        if numRows == 2:
            return [[1],[1,1]]
        dp = [None]*numRows
        dp[0] = [1]
        dp[1] = [1,1]
        for i in range(2,numRows):
            dp[i] = [0]*(i+1)
            dp[i][0] = 1
            dp[i][-1] = 1
            for j in range(1,i):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        return dp

2.6 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

1
2
3
4
5
6
7
8
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

1
2
输入：triangle = [[-10]]
输出：-10

链接:
https://leetcode-cn.com/problems/triangle/

提示：

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

进阶：

  • 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimumTotal(self, triangle):
        if len(triangle) == 0:
            return 0
        for i in range(1,len(triangle)):
            for j in range(len(triangle[i])):
                if j == 0:
                    triangle[i][0] += triangle[i-1][0]
                elif j == len(triangle[i])-1:
                    triangle[i][-1] += triangle[i-1][-1]
                else:
                    triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j])
        return min(triangle[-1])

2.7 摆动序列

https://leetcode-cn.com/problems/wiggle-subsequence/

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

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

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

示例 1：

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

示例 2：

1
2
3
4
输入：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：

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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

进阶：你能否用 O(n) 时间复杂度完成此题?

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def wiggleMaxLengthByDP(self, nums):
        if len(nums) < 2:
            return 0
        dp = [[0]*len(nums)for i in range(2)]
        dp[0][0] = 1
        dp[1][0] = 1
        for i in range(1,len(nums)):
            sub = nums[i] - nums[i-1]
            if sub > 0:
                dp[0][i] = dp[1][i-1] + 1
                dp[1][i] = dp[1][i-1]
            elif sub < 0:
                dp[1][i] = dp[0][i-1] + 1
                dp[0][i] = dp[0][i-1]
            else:
                dp[1][i] = dp[1][i-1]
                dp[0][i] = dp[0][i-1]
        return max(dp[0][-1],dp[1][-1])

if __name__ == '__main__':
    nums = [1,17,5,10,13,15,10,5,16,8]
    s = Solution()
    print(s.wiggleMaxLengthByDP(nums))

2.8 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

链接：
https://leetcode-cn.com/problems/word-break/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def wordBreak(self, s, wordDict):
        if len(s) == 0:
            return False
        strList = list(s)
        dp = [False] * (len(s))
        if s[0] in wordDict:
            dp[0] = True

        for i in range(1,len(s)):
            if ''.join(strList[:i+1]) in wordDict:
                dp[i] = True
                continue
            for j in range(i,-1,-1):
                if dp[j] == True and ''.join(strList[j+1:i+1]) in wordDict:
                    dp[i] = True
                    break
        return dp[-1]

if __name__ == "__main__":
    s = Solution()
    print(s.wordBreak("applepenapple",["apple","pen"]))

3. 子数组问题

3.1 子数组最大和

https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

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

示例 3：

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

示例 4：

1
2
输入：nums = [-1]
输出：-1

示例 5：

1
2
输入：nums = [-100000]
输出：-100000

提示：

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105
1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        for i in range(1,len(nums)):
            nums[i] = max(nums[i],nums[i-1]+nums[i])
            if nums[i] > maxSum:
                maxSum = nums[i]
        return maxSum

3.2 环形子数组最大和

https://leetcode-cn.com/problems/maximum-sum-circular-subarray/

给定一个由整数数组 A 表示的**环形数组 C**，求 **C** 的非空子数组的最大可能和。

在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）

此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

示例 1：

1
2
3
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

1
2
3
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

1
2
3
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

示例 4：

1
2
3
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

示例 5：

1
2
3
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1

提示：

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxSubarraySumCircular(self, nums):
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp1 = [0]*len(nums)
        dp2 = [0]*len(nums)
        maxSum1 = minSum = sum = dp1[0] = dp2[0] = nums[0]
        for i in range(1,len(nums)):
            dp1[i] = max(dp1[i-1]+nums[i],nums[i])
            maxSum1 = max(dp1[i], maxSum1)

            sum += nums[i]
            dp2[i] = min(dp2[i-1]+nums[i],nums[i])
            minSum = min(dp2[i], minSum)
        if sum == minSum:
            return maxSum1
        maxSum2 = sum - minSum
        return max(maxSum1,maxSum2)

if __name__ == "__main__":
    s = Solution()
    print(s.maxSubarraySumCircular([-2,-3,-1]))

3.3 乘积最大子数组

https://leetcode-cn.com/problems/maximum-product-subarray/

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        dpMax = [0]*len(nums)
        dpMin = [0]*len(nums)
        dpMax[0] = nums[0]
        dpMin[0] = nums[0]
        maxMulti = nums[0]
        for i in range(1,len(nums)):
            dpMin[i] = min(nums[i] * dpMin[i-1], nums[i] * dpMax[i-1], nums[i])
            dpMax[i] = max(nums[i] * dpMax[i-1], nums[i] * dpMin[i-1], nums[i])
            maxMulti = max(dpMax[i], maxMulti)
        print(dpMin,dpMax)
        return maxMulti

3.4 乘积为正的最长子串长度

https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

示例 1：

1
2
3
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

示例 2：

1
2
3
4
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

示例 3：

1
2
3
输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

示例 4：

1
2
输入：nums = [-1,2]
输出：1

示例 5：

1
2
输入：nums = [1,2,3,5,-6,4,0,10]
输出：4

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def getMaxLen(self, nums):
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            if nums[0] >=0:
                return 1
            else:
                return 0
        positiveDP = [0] * len(nums)
        negativeDP = [0] * len(nums)
        if nums[0] == 0:
            positiveDP[0] = 0
            negativeDP[0] = 0
        elif nums[0] > 0:
            positiveDP[0] = 1
            negativeDP[0] = 0
        else:
            positiveDP[0] = 0
            negativeDP[0] = 1
        longestLne = 0
        for i in range(1,len(nums)):
            if nums[i] == 0:
                positiveDP[i] = 0
                negativeDP[i] = 0
            elif nums[i] > 0:
                positiveDP[i] = positiveDP[i-1] + 1
                if negativeDP[i-1] == 0:
                    negativeDP[i] = 0
                else:
                    negativeDP[i] = negativeDP[i-1] + 1
            else:
                negativeDP[i] = positiveDP[i-1] + 1
                if negativeDP[i-1] == 0:
                    positiveDP[i] = 0
                else:
                    positiveDP[i] = negativeDP[i-1] + 1
            longestLne = max(longestLne,positiveDP[i])
        return longestLne

3.5 最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

解:

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

3.6 摆动序列

https://leetcode-cn.com/problems/wiggle-subsequence/

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

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

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

示例 1：

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

示例 2：

1
2
3
4
输入：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：

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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

解:

可贪心可动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def wiggleMaxLength(self, nums):
        dp = [[1 for row in range(len(nums))]for col in range(2)]
        for i in range(1,len(nums)):
            if nums[i] > nums[i-1]:
                dp[0][i] = dp[1][i-1] + 1
                dp[1][i] = dp[1][i-1]
            elif nums[i] < nums[i-1]:
                dp[0][i] = dp[0][i-1]
                dp[1][i] = dp[0][i-1] + 1
            else:
                dp[0][i] = dp[0][i-1]
                dp[1][i] = dp[1][i-1]
        return max(dp[0][-1],dp[1][-1])

3.7 等差数列划分

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

  • 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

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

示例 1：

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

示例 2：

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

链接:
https://leetcode-cn.com/problems/arithmetic-slices/

提示：

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numberOfArithmeticSlices(self, nums):
        if len(nums) < 3:
            return 0
        dp = [0] * len(nums)
        output = 0
        for i in range(1,len(nums)-1):
            if nums[i] - nums[i-1] == nums[i+1] - nums[i]:
                dp[i] = dp[i-1] + 1
                output += dp[i]
            else:
                dp[i] = 0
        return output

4. 回文串与编辑问题

4.1 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

给你一个字符串 s，找到 s 中最长的回文子串。

与647. 回文子串类似

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "aa"
输出："aa"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

解:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
    # 双指针中心扩散法
    def longestPalindromeByCD(self, s):
        if len(s) == 0:
            return ''
        if len(s) == 1:
            return s
        self.longestStr = ''
        for center in range(len(s)-1):
            self.centralDiffusion(s,center,center)
            self.centralDiffusion(s,center,center + 1)
        return self.longestStr

    def centralDiffusion(self,s,leftP,rightP):
        while leftP >=0 and rightP < len(s):
            if s[leftP] != s[rightP]:
                break
            if rightP - leftP +1 > len(self.longestStr):
                self.longestStr = s[leftP:rightP+1]
            leftP  -= 1
            rightP += 1
            
    # 动态规划
    def longestPalindromeByDP(self, s):
        if len(s) == 0:
            return ''
        if len(s) == 1:
            return s
        longestLen = 1
        leftP = 0
        rightP = 0
        dp = [[False for row in range(len(s))] for col in range(len(s))]
        for col in range(len(s)):
            for row in range(len(s)):
                if col < row:
                    continue
                if col == row:
                    dp[row][col] = True
                elif s[col] == s[row] and (col - row == 1 or dp[row+1][col-1]):
                    dp[row][col] = True
                else:
                    dp[row][col] = False
                if dp[row][col] == True and col - row + 1 > longestLen:
                    longestLen = col - row + 1
                    leftP = row
                    rightP = col
        return s[leftP:rightP+1]

if __name__ == "__main__":
    s = Solution()
    s.longestPalindromeByDP("aa")

4.2 最长回文子序列

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成
  • 与16题不同点在于，16题的子串必须连续，本题则不需要

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) < 2:
            return len(s)
        dp = [[0 for row in range(len(s))] for col in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for row in range(len(s)-1,-1,-1):
            for col in range(row+1,len(s)):
                if s[col] == s[row]:
                    dp[row][col] = dp[row+1][col-1] + 2
                else:
                    dp[row][col] = max(dp[row+1][col], dp[row][col-1])
        return dp[0][-1]

4.3 最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

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

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

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

解:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or text2 == 0:
            return 0
        dp = [[0 for row in range(len(text2)+1)] for col 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][j-1], dp[i-1][j])
        return dp[-1][-1]

4.4 编辑距离

https://leetcode-cn.com/problems/edit-distance/

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

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

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

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if word1 == word2:
            return 0
        if word1 == 0 or word2 == 0:
            return len(word1) + len(word2)
        dp = [[0 for row in range(len(word2)+1)] for col in range(len(word1)+1)]
        for i in range(1,len(word1)+1):
            dp[i][0] = i
        for j in range(1,len(word2)+1):
            dp[0][j] = j
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) +1
        return dp[-1][-1]

5. 股票问题

5.1 买卖股票的最佳时机I

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        dp = [0]*len(prices)
        dp[0] = prices[0]
        maxValue = 0
        for i in range(1,len(prices)):
            dp[i] = min(dp[i-1], prices[i])
            maxValue = max(maxValue, prices[i] - dp[i])
        return maxValue
    
    def maxProfitByGreedy(self, prices):
        if len(prices) < 2:
            return 0
        maxProfit = 0
        minValue = prices[0]
        for i in range(len(prices)):
            minValue = min(minValue, prices[i])
            maxProfit = max(maxProfit, prices[i]-minValue)
        return maxProfit

5.2 买卖股票的最佳时机II

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

示例 1:

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

示例 2:

1
2
3
4
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

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

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104
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
26
27
28
class Solution:
    def maxProfitByGreedy(self, prices):
        if len(prices) < 2:
            return 0
        maxProfit = 0
        for i in range(1,len(prices)):
            profit = prices[i] - prices[i-1]
            if profit > 0:
                maxProfit += profit
        return maxProfit

    def maxProfitByDP(self, prices):
        if len(prices) < 2:
            return 0
        dp = [0]*len(prices)
        dp[0] = prices[0]
        maxValue = 0
        maxProfit = 0
        for i in range(1,len(prices)):
            dp[i] = min(dp[i-1], prices[i])
            if prices[i] - dp[i] < maxValue:
                maxProfit += maxValue
                dp[i] = prices[i]
                maxValue = 0
            else:
                maxValue = prices[i] - dp[i]
        maxProfit += maxValue
        return maxProfit

5.3 买卖股票的最佳时机III

描述:
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

1
2
3
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

链接:

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        dp = [[0 for col in range(len(prices))] for row in range(2)]
        dp[0][0] = -prices[0]
        dp[1][0] = 0
        dp[0][1] = max(dp[0][0], dp[1][0]-prices[1])
        dp[1][1] = max(dp[1][0], dp[0][0]+prices[1])

        for i in range(2,len(prices)):
            dp[0][i] = max(dp[0][i-1], dp[1][i-2]-prices[i])
            dp[1][i] = max(dp[1][i-1], dp[0][i-1]+prices[i])
        return max(dp[0][-1],dp[1][-1])

5.4 买卖股票的最佳时机IV

描述:
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。
如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：
这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

链接:
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

示例 1：

1
2
3
4
5
6
7
8
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

1
2
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices, fee):
        if len(prices) < 2:
            return 0
        dp = [[0 for col in range(len(prices))]for row in range(2)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0

        for i in range(1,len(prices)):
            dp[0][i] = max(dp[0][i-1],dp[1][i-1]-prices[i])
            dp[1][i] = max(dp[1][i-1],dp[0][i-1]+prices[i]-fee)
        return max(dp[0][-1], dp[1][-1])

6. 背包问题

背包问题分类

6.1 0/1背包问题

6.1.0 原型

6.1.0.1 题目描述

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

**例如:**背包最大重量为4。
物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

6.1.0.2 题目分析

  1. 确定dp数组以及下标的含义
    使用二维数组，即:
    dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
    image-20211009160154930

  2. 确定递推公式
    两种情况:

  • 不放物品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数组如何初始化

    • 首先从dp[i][j]的定义出发
      如果背包容量j为0的话，即dp[i][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物品。

    image-20211009160811954

  2. 确定遍历顺序
    递推方向如下

    image-20211009161003391
    所以：
    先遍历物品还是先遍历背包重量其实都可以
    但是先遍历物品更好理解

  3. 举例推导dp数组

    image-20211009161539532

6.1.0.3 代码实现

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def zero_oneBackpackProblem(self, weight, value, volume):
        dp = [0] * (volume + 1)
        for j in range(1,len(dp)):
            if j >= weight[0]:
                dp[j] = value[0]
        for i in range(len(weight)):
            print(dp)
            for j in range(volume,1,-1):
                if weight[i] > j:
                    break
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
        print(dp)
        return dp[-1]

if __name__ == "__main__":
    wight = [1,3,4]
    value = [15,20,30]
    volume = 4
    s = Solution()
    print(s.zero_oneBackpackProblem(wight,value,volume))

6.2 完全背包问题

6.2.0 原型

6.2.0.1 题目描述

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

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

例如:
背包最大重量为4。

物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个！

问背包能背的物品最大价值是多少？

6.2.0.2 题目分析

和01背包问题不同的地方就是: 每种物品有无限件
这导致了在实现上有两点不同:

  • dp初始化不同

    • 0-1背包的物体只能使用一次，所以初始化第一排(物体0)时：
    1
    2
    3
    dp = [0] * (volume + 1)
    for j in range(weight[0],len(dp)):
    	dp[j] = value[0]

    ​ 只需要装入一次，然后价值就不变了，都是value[0]

    • 完全背包的物体可以多次使用，因此初始化第一排(物体0)时：

      1
      2
      3
      dp = [0] * (volume + 1)
      for j in range(weight[0],len(dp)):
      	dp[j] = dp[j-weight[0]] + value[0]

      要考虑多次装入，更新价值

  • dp迭代顺序不同

    • 01背包物体只能使用一次，迭代时为了保证不重复装入，需要逆序:

      1
      2
      3
      4
      5
      for i in range(1,len(weight)):
          for j in range(volume,1,-1):
              if weight[i] > j:
                  break
              dp[j] = max(dp[j],dp[j-weight[i]]+value[i])

    • 完全背包的物体可以多次使，正序遍历即可:

      1
      2
      3
      for i in range(1,len(weight)):
          for j in range(wight[i],volume+1):
      		dp[j] = max(dp[j],dp[j-weight[i]]+value[i])

      剩下的就完全一样了。

6.2.0.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def completeBackpack(self, weight, value, volume):
        dp = [0] * (volume + 1)
        for j in range(weight[0],len(dp)):
            dp[j] = dp[j-weight[0]] + value[0]
        for i in range(len(weight)):
            print(dp)
            for j in range(wight[i],volume+1):
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
        print(dp)
        return dp[-1]
    
if __name__ == "__main__":
    wight = [1,3,4]
    value = [15,20,30]
    volume = 4
    s = Solution()
    print(s.completeBackpack(wight,value,volume))

6.2.1 零钱兑换 I

https://leetcode-cn.com/problems/coin-change/

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0
        if len(coins) == 0:
            return -1
        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
        return dp[-1]

6.2.2 零钱兑换 II

https://leetcode-cn.com/problems/coin-change-2/

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

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

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

解:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def change(self, amount, coins):
        if len(coins) == 0 or amount == 0:
            return 1
        dp = [0] * (amount+1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin,amount+1):
                dp[j] += dp[j-coin]
        return dp[-1]

6.2.3 组合总和 Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

进阶：
如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

解:

与 6.2.2 零钱兑换 同类型，完全背包下：

  • 求组和：背包在内，物品在外
  • 求排列：背包在外，物品在内
1
2
3
4
5
6
7
8
9
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i - num]
        return dp[-1]

6.2.4 整数拆分

https://leetcode-cn.com/problems/integer-break/

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。
返回你可以获得的最大乘积。

示例 1:

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

解:

状态定义：
dp[i]： n=i 时的最大乘积

状态转移：
遍历1~i之间所有的因子j,则i可以被拆为 j 与 i-j两数的和, 其中i-j假设也可以被拆分，则取dp[i-j]，遍历j，取最大的dp[i]
dp[i] = max(dp[i],j*(i-j), dp[j]*(i-j))

边界条件：
dp[0]=dp[1]=0
时间：O(n)
空间：O(n)

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

6.2.5 完全平方数

https://leetcode-cn.com/problems/perfect-squares/

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 104

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n + 1)]
        # dp[0] = 0 无意义，只是为了方便记录特殊情况:
        # n本身就是完全平方数，dp[n] = min(dp[n], dp[n - n] + 1) = 1

        for i in range(1, n): # 遍历物品
            if i * i > n:
                break
            num = i * i
            for j in range(num, n + 1): # 遍历背包
                dp[j] = min(dp[j], dp[j - num] + 1)
        return dp[n]

7. 复合问题

7.1 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

链接:
https://leetcode-cn.com/problems/trapping-rain-water/

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height):
        if len(height) < 3:
            return 0
        dp = [[0 for row in range(len(height))] for col in range(2)]
        dp[0][0] = 0
        dp[1][-1] = 0
        lenth = len(height)
        for i in range(1,lenth):
            dp[0][i] = max(dp[0][i-1],height[i-1])
            dp[1][lenth-1-i] = max(dp[1][lenth-i],height[lenth-i])
        output = 0
        for i in range(1,lenth-1):
            rain = min(dp[0][i],dp[1][i]) - height[i]
            if rain > 0:
                output += rain
        return output

7.2 不同的二叉搜索树

描述:
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

链接：
https://leetcode-cn.com/problems/unique-binary-search-trees/

提示：

  • 1 <= n <= 19

解：
卡特兰公式
明确：
二叉搜索树序列的个数与其值无关，只与区间长度有关

例如：我们在计算序列长度为 4 的二叉搜索树[1 , 2 , 3 , 4 ]。
假设以 1 作为根结点，则左子树序列长度为 0 ，右子树序列长度为 3 ，而我们之前就已经计算过序列长度为 3 的总个数了，没有必要再算一次，且当前状态受上一个状态的影响，因此我们就可以从这里入手，进行下一步优化——动态规划。

定义两个函数：

  • G(n)：
    长度为 n 的序列能构成的不同二叉搜索树的个数

  • F(i,n)：
    以 i 为根、序列长度为 n 的不同二叉搜索树的个数(1≤i≤n)。

首先，根据方法一的思路可以知道，对于不同的二叉搜索树的总数G(n) ，是所有F(i,n) 之和：

$G(n)=\displaystyle\sum^n_{i=0} F(i,n)$

对于边界情况，当序列长度为$ 1 $( 只有根 ) 或为 0 ( 空树 ) 时，只有一种情况，即：

G(0) = 1，G(1) = 1

举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 [1, 2, 3, 4, 5, 6, 7]，我们需要从左子序列 [1, 2][1,2] 构建左子树，从右子序列 [4, 5, 6, 7]构建右子树，然后将它们组合（即笛卡尔积）。

对于这个例子，不同二叉搜索树的个数为 F(3, 7)。
我们将 [1,2] 构建不同左子树的数量表示为 G(2), 从 [4, 5, 6, 7]构建不同右子树的数量表示为 G(4)，注意到G(n) 和序列的内容无关，只和序列的长度有关。
于是，$F(3,7) = G(2) \cdot G(4)$。
因此，我们可以得到以下公式：

$F(i,n) = G(i-1) \cdot G(n-i)$

因此，结合上述公式可以得出递归表达式：

$G(n) = \displaystyle \sum^{n}_{i=1}{G(i-1) \cdot G(n-i)}$

于是，我们可以从小到大计算GG函数，

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

22. 解码方法

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

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

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

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

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

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

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

示例 1：

1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

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

示例 3：

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

示例 4：

1
2
3
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

链接:
https://leetcode-cn.com/problems/decode-ways/

提示：

  • 1 <= s.length <= 100
  • s 只包含数字，并且可能包含前导零。