抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

blaire

👩🏻‍💻星洲小课堂 SinClass

Home

Categories

Friends

Skills

Careers

Tweet

Summary 20 dynamic programming

blairchen
leetcode

Publish：Aug 31, 2019
views
image

使用动态规划解决问题一般分为三步：

  1. 表示状态
  2. 找出状态转移方程
  3. 边界处理

表示状态

分析问题的状态时，不要分析整体，只分析最后一个阶段即可！因为动态规划问题都是划分为多个阶段的，各个阶段的状态表示都是一样，而我们的最终答案在就是在最后一个阶段。

  1. 爬楼梯 climbing-stairs ， ✔️ 新建{}or[] ,滚动数组
  2. 不同路径 II ， ✔️
  3. 编辑距离 ， ✔️
  4. 扔鸡蛋
  5. 连续子数组的最大和 // dp: F[i] = max(a[i], F[i-1]+a[i]);
  6. Longest Palindromic Substring/最长回文子串
  7. Edit Distance/编辑距离
  8. Distinct Subsequences/不同子序列
  9. Interleaving String/交错字符串
  10. 把数字翻译成字符串
  11. Leetcode 64. Minimum Path Sum, 最小路径和
  12. 115. Distinct Subsequences I (Hard)
  13. 940. 不同的子序列 II (Hard)

不同路径 II：

image

如果当前没有障碍物，dp[m][n] = dp[m - 1][n] + dp[m][n - 1]
如果有障碍物，则dp[m][n] = 0

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
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        #新建矩阵版
        height, width = len(obstacleGrid),len(obstacleGrid[0])
        store = [[0]*width for i in range(height)]

        #从上到下，从左到右
        for m in range(height):#每一行
            for n in range(width):#每一列
                if not obstacleGrid[m][n]: #如果这一格没有障碍物
                    if m == n == 0: #或if not(m or n)
                        store[m][n] = 1
                    else:
                        a = store[m-1][n] if m!=0 else 0 #上方格子
                        b = store[m][n-1] if n!=0 else 0 #左方格子
                        store[m][n] = a+b
        return store[-1][-1]

编辑距离：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

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

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

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

如果单词1第i+1个字符和单词2第j+1个字符相同，那么就不用操作，则DP[i + 1][j + 1] = DP[i][j];

如果不相同,则有三种可能操作，即增，删，替换。则取这三种操作的最优值，即dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i + 1][j]));

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
class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)
        
        # 有一个字符串为空串
        if n * m == 0:
            return n + m
        
        # dp 数组
        dp = [ [0] * (m + 1) for _ in range(n + 1)]
        
        # 边界状态初始化
        for i in range(n + 1):
            dp[i][0] = i
        for j in range(m + 1):
            dp[0][j] = j
        
        # 计算所有 DP 值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = dp[i - 1][j] + 1
                right = dp[i][j - 1] + 1
                left_right = dp[i - 1][j - 1] 
                if word1[i - 1] != word2[j - 1]:
                    left_right += 1
                dp[i][j] = min(left, right, left_right)
        
        return dp[n][m]

二维DP

布尔数组

(1). Longest Palindromic Substring/最长回文子串 ， P(i,j)=P(i+1,j−1)∧(Si==Sj)P(i,j)=P(i+1,j−1)∧(Si == Sj)

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 longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            sub_len = l+1
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if sub_len == 1:
                    dp[i][j] = True
                elif sub_len == 2:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and sub_len > len(ans):
                    ans = s[i:j+1] # "abcd"[1:2] = b
        return ans

(2). Interleaving String/交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

1
2
3
4
5
6
7
8
示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

解决这个问题的正确方法是动态规划。 首先如果 ∣s1∣+∣s2∣≠∣s3∣|s_1| + |s_2| \neq |s_3|, 那 s3s_3 必然不可能由 s1s_1 和 s2s_2 交错组成。在 ∣s1∣+∣s2∣=∣s3∣|s_1| + |s_2| = |s_3|时，我们可以用动态规划来求解。我们定义 f(i,j)f(i,j) 表示 s1s_1 的前 ii 个元素和 s2s_2 的前 jj 个元素是否能交错组成 s3s_3 的前 i+ji + j 个元素。如果 s1s_1 的第 ii 个元素和 s3s_3 的第 i+ji+j 个元素相等，那么 s1s_1 的前 ii 个元素和 s2s_2 的前 jj 个元素是否能交错组成 s3s_3 的前 i+ji+j 个元素取决于 s1s_1 的前 i−1i−1 个元素和 s2s_2 的前 jj 个元素是否能交错组成 s3s_3 的前 i+j−1i + j - 1 个元素，即此时 f(i,j)f(i, j) 取决于 f(i−1,j)f(i - 1, j)，在此情况下如果 f(i−1,j)f(i - 1, j) 为真，则 f(i,j)f(i, j) 也为真。同样的，如果 s2s_2 的第 jj 个元素和 s3s_3 的第 i+ji + j 个元素相等并且 f(i,j−1)f(i, j - 1) 为真，则 f(i,j)f(i, j) 也为真。于是我们可以推导出这样的动态规划转移方程：

f(i,j)=[f(i−1,j) and s1(i−1)=s3(p)] or [f(i,j−1) and s2(j−1)=s3(p)]f(i, j) = [f(i - 1, j) \, {\rm and} \, s_1(i - 1) = s_3(p)] \, {\rm or} \, [f(i, j - 1) \, {\rm and} \, s_2(j - 1) = s_3(p)]

其中 p=i+j−1p = i + j - 1。边界条件为 f(0,0)=Truef(0, 0) = {\rm True}。至此，我们很容易可以给出这样一个实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        len1=len(s1)
        len2=len(s2)
        len3=len(s3)
        if(len1+len2!=len3):
            return False
        dp=[[False]*(len2+1) for i in range(len1+1)]
        dp[0][0]=True
        for i in range(1,len1+1):
            dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])
        for i in range(1,len2+1):
            dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])
        for i in range(1,len1+1):
            for j in range(1,len2+1):
                dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])
        return dp[-1][-1]

(3). 剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

分析摘要： 要的是种类总数，并不是要的是详细列表，这类问题，常见方案是： 动态规划

分类计数：

dp[i] 表示 nums[0…i]

dp[i] = dp[i-1] + dp[i-2]

1
2
3
4
5
6
7
8
9
10
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            tmp = s[i - 2:i]
            c = a + b if "10" <= tmp <= "25" else a
            b = a
            a = c
        return a

数字数组

  1. Leetcode 64. Minimum Path Sum, 最小路径和 矩阵左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。

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

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

示例:

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

12. 不同的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1：

输入：S = "rabbbit", T = "rabbit"
输出：3
解释：

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串组成最多个数.

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

所以动态方程:

当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];

当 S[j] != T[i] , dp[i][j] = dp[i][j-1]

举个例子,如示例的

Reference

This blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) license.

The permanent link to this article is：http://www.sinclass.com/2019/08/31/leetcode/summary_dp/

updated on：Jun 28, 2021

dynamic programming

Comments