Dynamic Programming

Posted on | In | |
DP understanding and practices

动态规划，无非就是利用历史记录，来避免我们的重复计算。

  1. 最优子结构。最优子结构指的是问题的最优解包含子问题的最优解。反过来说，我们可以通过子问题的最优解来推导出问题的最优解。或者理解为后面阶段的状态可以由前面阶段的状态推导出来。
  2. 无后效性。在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。同时，某阶段的状态值一旦确定，就不受之后阶段的决策影响。
  3. 重复子问题。不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

动态规划三大步骤

  1. 第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定这个数组元素的含义，例如 dp[i] 是代表什么意思？
  2. 第二步骤：找出状态转移方程。当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
  3. 第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

案例

leetcode 70 Climbing Stairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
  1. 定义数组元素的含义
    我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。
  2. 找出数组元素间的关系式
    青蛙到达第 n 级的台阶有两种方式: 从第 n-1 级跳上来 和 从第 n-2 级跳上来。因此关系式为：
  3. 找出初始条件
    dp[0] = 0. dp[1] = 1. 即 n <= 1 时，dp[n] = n.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [-1] * (n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

leetcode 62 Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
问题描述：

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?
Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:

Input: m = 7, n = 3
Output: 28
  1. 定义数组元素的含义
    当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i][j] 种路径
  2. 找出关系数组元素间的关系式
  3. 找出初始值
  • dp[0][0…n-1] = 1; // 相当于最上面一行，机器人只能一直往左走
  • dp[0…m-1][0] = 1; // 相当于最左面一列，机器人只能一直往下走
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if not m or not n:
            return 1
        
        dp = [[1] * n for i 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]

leetcode 64 Minimum Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
问题描述：

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
  1. 定义数组元素的含义
    当机器人从左上角走到(i, j) 这个位置时，最小的路径和是 dp[i][j]
  2. 找出关系数组元素间的关系式
    由于机器人可以向下走或者向右走，所以有两种方式到达:
  • 一种是从 (i-1, j) 这个位置走一步到达
  • 一种是从(i, j - 1) 这个位置走一步到达
    不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的，那么我们要从这两种方式中，选择一种，使得dp[i][j] 的值是最小的，显然有:
  1. 找出初始值
  • dp[0][j] = arr[0][j] + dp[0][j-1]; // 相当于最上面一行，机器人只能一直往左走
  • dp[i][0] = arr[i][0] + dp[i][0]; // 相当于最左面一列，机器人只能一直往下走
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        dp = [[0] * n for i in range(m)]
        
        ## initialize 
        dp[0][0] = grid[0][0]
        for i in range(1,n):
            dp[0][i] = grid[0][i] + dp[0][i-1]
        
        for j in range(1,m):
            dp[j][0] = grid[j][0] + dp[j-1][0]
        
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
        
        return dp[-1][-1]

leetcode 72 Edit Distance

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
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
  1. 定义数组元素的含义
    当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i][j]
  2. 找出关系数组元素间的关系式
    比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i][j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，从规模小的，通过一些操作，推导出规模大的。对于这道题，我们可以对 word1 进行三种操作:
    • 插入一个字符
    • 删除一个字符
    • 替换一个字符
    1. 如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作。
    2. 如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
      • 如果把字符 word1[i] 替换成与 word2[j] 相等，则有
      • 如果在字符串word1末尾插入一个与 word2[j] 相等的字符，则有:
      • 如果把字符 word1[i] 删除，则有:那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有:
  3. 找出初始值
    我们的初始值是计算出所有的 dp[0] [0…n] 和所有的 dp[0…m][0]。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        len_word2 = len(word2)
        len_word1 = len(word1)
            
        dp = [[0] * (len_word2+1) for i in range(len_word1+1)]
       
        for j in range(1,len_word2+1):
            dp[0][j] = dp[0][j-1]+1
        
        for i in range(1,len_word1+1):
            dp[i][0] = dp[i-1][0] + 1
            
        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-1][j-1],dp[i][j-1],dp[i-1][j]]) + 1
        
        return dp[-1][-1]

reference from https://zhuanlan.zhihu.com/p/91582909