0%

Dynamic Programming

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

  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 级跳上来。因此关系式为: \[dp[n] = dp[n-1] + dp[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. 找出关系数组元素间的关系式 \[dp[i][j] = dp[i-1][j] + dp[i][j-1]\]
  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] 的值是最小的,显然有: \[dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[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] 相等,这个时候不需要进行任何操作。 \[dp[i][j] = dp[i-1][j-1]\]
    2. 如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
      • 如果把字符 word1[i] 替换成与 word2[j] 相等,则有 \[dp[i][j] = dp[i-1][j-1] + 1\]
      • 如果在字符串word1末尾插入一个与 word2[j] 相等的字符,则有: \[dp[i][j] = dp[i] [j-1] + 1\]
      • 如果把字符 word1[i] 删除,则有: \[dp[i][j] = dp[i-1] [j] + 1\] 那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有: \[dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[[i-1][j]]) + 1\]
  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