leetcode-DynamicProgramming

动态规划和贪心算法

贪心算法

使用局部最优，推出全局最优算法

分发饼干

1

用最少数量的箭引爆气球

1

动态规划

基础套路

1.dp数组的定义和下标。【非常重要】

2.递推公式。

3.dp数组如何初始化，初始化也需要注意。【从哪里初始化，初始化后该如何使用，这要参考dp数组的定义】

4.遍历顺序，比较考究，01 先遍历背包，后遍历物品。

4.1排列和组合的遍历顺序是不相同的。
        
4.1.1 排列：背包在外 物品在内。（322）
        
4.1.2 组合：物品在外，背包在内。（518）

5.（出现问题）打印dp数组。（打印dp数组，检查是否有问题，检验1 2 3 4 步骤）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

带有备忘录的动规划(优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fib(N: int) -> int:
    # 备忘录全初始化为 0
    memo = [0] * (N + 1)
    # 进行带备忘录的递归
    return dp(memo, N)

# 带着备忘录进行递归
def dp(memo: List[int], n: int) -> int:
    # base case
    if n == 0 or n == 1: return n
    # 已经计算过，不用再计算了
    if memo[n] != 0: return memo[n]
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2)
    return memo[n]

初级题目

爬楼梯

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# dp[i]： 爬到第i层楼梯，有dp[i]种方法
# 每次爬1个或者2个台阶


# 爬到第i层的方法 = 爬到第i-1层的方法（然后再往上爬1个台阶）+ 爬到第i-2层的方法（然后再往上爬2个台阶）
# 动态规划递推公式：dp[i] = dp[i-1] + dp[i-2]
# 空间复杂度为O(n)版本
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

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
# 定义状态（定义子问题）
# dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。

# 状态转移方程（描述子问题之间的联系）考虑dp[i-1]和dp[i]的关系

# 1. dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；
# 2. dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]

# dp[i] = dp[i−1] + nums[i], if dp[i−1] > 0
# dp[i] = nums[i], if dp[i−1] <= 0
​
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] >= 0:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)

不同路径

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

image- 
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
# 机器人只能向下或者向右移动，因此在二维网格nums[i][j]中

# dp[i][j]的定义：到nums[i][j]一共有dp[i][j]个方法。

# 向下：nums[i-1][j] -> nums[i][j]: dp[i-1][j]个方法
# 向右：nums[i][j-1] -> nums[i][j]：dp[i][j-1]个方法

# 递推关系：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
# 需要初始化dp数组
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        initialize dp[i][j]
        in top, in left we have only 1 path

        dp[i][j] = the step to reach [i,j]
        dp[i][j] = dp[i-1][j] move right + dp[i][j-1] move bottom

        """
        dp = [[0 for i in range(n)] for j in range(m)]
        
        for j in range(m):
            dp[j][0] = 1

        for i in range(n):
            dp[0][i] = 1

        # print(dp)
        for i in range(1,m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                # print(dp)
        return dp[-1][-1]


中级题目

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 状态定义：dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。
# 当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
# 当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp = [1] * len(nums)

        result = 0
        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


给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符
image- 
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
# dp[i][j]定义：word1 到 i 位置转换成 word2 到 j 位置需要最少步数

# 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]，继承前一步骤的步数。
# 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

# dp[i-1][j-1] 表示替换操作，
# dp[i-1][j] 表示删除操作，
# dp[i][j-1] 表示插入操作。

# dp数组的初始化：第一行，第一列要单独考虑，引入 ''，因为第一行和第一列只需要一步替换
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # 第一行
        for j in range(1, n2 + 1):
            dp[0][j] = dp[0][j-1] + 1
        # 第一列
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i-1][0] + 1
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 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
        #print(dp)      
        return dp[-1][-1]

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。

image- 
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
# dp数组定义：在[i][j]的位置上，dp[i][j]为当前最小路径和
# 向下：dp[i-1][j] + grid[i][j]
# 向左：dp[i][j-1] + grid[i][j]
# 当前最小路径和：p[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # print(dp)
        res = 0
        for i in range(m):
            res += grid[i][0]
            dp[i][0] = res
        
        res = 0
        for j in range(n):
            res += grid[0][j]
            dp[0][j] = res
        
        for i in range(1,m):
            for j in range(1,n):
                    dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])
        # print(dp)
        return dp[-1][-1]

高级题目

1