动态规划

背景

先从一道题目开始~
如题 triangle
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如,给定三角形:
1
[
2
[2],
3
[3,4],
4
[6,5,7],
5
[4,1,8,3]
6
]
Copied!
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
使用 DFS(遍历 或者 分治法)
遍历
image.png
分治法
image.png
优化 DFS,缓存已经被计算的值(称为:记忆化搜索 本质上:动态规划)
image.png
动态规划就是把大问题变成小问题,并解决了小问题重复计算的方法称为动态规划
动态规划和 DFS 区别
  • 二叉树 子问题是没有交集,所以大部分二叉树都用递归或者分治法,即 DFS,就可以解决
  • 像 triangle 这种是有重复走的情况,子问题是有交集,所以可以用动态规划来解决
动态规划,自底向上
1
func minimumTotal(triangle [][]int) int {
2
if len(triangle) == 0 || len(triangle[0]) == 0 {
3
return 0
4
}
5
// 1、状态定义:f[i][j] 表示从i,j出发,到达最后一层的最短路径
6
var l = len(triangle)
7
var f = make([][]int, l)
8
// 2、初始化
9
for i := 0; i < l; i++ {
10
for j := 0; j < len(triangle[i]); j++ {
11
if f[i] == nil {
12
f[i] = make([]int, len(triangle[i]))
13
}
14
f[i][j] = triangle[i][j]
15
}
16
}
17
// 3、递推求解
18
for i := len(triangle) - 2; i >= 0; i-- {
19
for j := 0; j < len(triangle[i]); j++ {
20
f[i][j] = min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
21
}
22
}
23
// 4、答案
24
return f[0][0]
25
}
26
func min(a, b int) int {
27
if a > b {
28
return b
29
}
30
return a
31
}
Copied!
动态规划,自顶向下
1
// 测试用例:
2
// [
3
// [2],
4
// [3,4],
5
// [6,5,7],
6
// [4,1,8,3]
7
// ]
8
func minimumTotal(triangle [][]int) int {
9
if len(triangle) == 0 || len(triangle[0]) == 0 {
10
return 0
11
}
12
// 1、状态定义:f[i][j] 表示从0,0出发,到达i,j的最短路径
13
var l = len(triangle)
14
var f = make([][]int, l)
15
// 2、初始化
16
for i := 0; i < l; i++ {
17
for j := 0; j < len(triangle[i]); j++ {
18
if f[i] == nil {
19
f[i] = make([]int, len(triangle[i]))
20
}
21
f[i][j] = triangle[i][j]
22
}
23
}
24
// 递推求解
25
for i := 1; i < l; i++ {
26
for j := 0; j < len(triangle[i]); j++ {
27
// 这里分为两种情况:
28
// 1、上一层没有左边值
29
// 2、上一层没有右边值
30
if j-1 < 0 {
31
f[i][j] = f[i-1][j] + triangle[i][j]
32
} else if j >= len(f[i-1]) {
33
f[i][j] = f[i-1][j-1] + triangle[i][j]
34
} else {
35
f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j]
36
}
37
}
38
}
39
result := f[l-1][0]
40
for i := 1; i < len(f[l-1]); i++ {
41
result = min(result, f[l-1][i])
42
}
43
return result
44
}
45
func min(a, b int) int {
46
if a > b {
47
return b
48
}
49
return a
50
}
Copied!

递归和动规关系

递归是一种程序的实现方式:函数的自我调用
1
Function(x) {
2
...
3
Funciton(x-1);
4
...
5
}
Copied!
动态规划:是一种解决问 题的思想,大规模问题的结果,是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)

使用场景

满足两个条件
  • 满足以下条件之一
    • 求最大/最小值(Maximum/Minimum )
    • 求是否可行(Yes/No )
    • 求可行个数(Count(*) )
  • 满足不能排序或者交换(Can not sort / swap )
如题:longest-consecutive-sequence 位置可以交换,所以不用动态规划

四点要素

  1. 1.
    状态 State
    • 灵感,创造力,存储小规模问题的结果
  2. 2.
    方程 Function
    • 状态之间的联系,怎么通过小的状态,来算大的状态
  3. 3.
    初始化 Intialization
    • 最极限的小状态是什么, 起点
  4. 4.
    答案 Answer
    • 最大的那个状态是什么,终点

常见四种类型

  1. 1.
    Matrix DP (10%)
  2. 2.
    Sequence (40%)
  3. 3.
    Two Sequences DP (40%)
  4. 4.
    Backpack (10%)
注意点
  • 贪心算法大多题目靠背答案,所以如果能用动态规划就尽量用动规,不用贪心算法

1、矩阵类型(10%)

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
思路:动态规划 1、state: f[x][y]从起点走到 x,y 的最短路径 2、function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y] 3、intialize: f[0][0] = A[0][0]、f[i][0] = sum(0,0 -> i,0)、 f[0][i] = sum(0,0 -> 0,i) 4、answer: f[n-1][m-1]
1
func minPathSum(grid [][]int) int {
2
// 思路:动态规划
3
// f[i][j] 表示i,j到0,0的和最小
4
if len(grid) == 0 || len(grid[0]) == 0 {
5
return 0
6
}
7
// 复用原来的矩阵列表
8
// 初始化:f[i][0]、f[0][j]
9
for i := 1; i < len(grid); i++ {
10
grid[i][0] = grid[i][0] + grid[i-1][0]
11
}
12
for j := 1; j < len(grid[0]); j++ {
13
grid[0][j] = grid[0][j] + grid[0][j-1]
14
}
15
for i := 1; i < len(grid); i++ {
16
for j := 1; j < len(grid[i]); j++ {
17
grid[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
18
}
19
}
20
return grid[len(grid)-1][len(grid[0])-1]
21
}
22
func min(a, b int) int {
23
if a > b {
24
return b
25
}
26
return a
27
}
Copied!
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径?
1
func uniquePaths(m int, n int) int {
2
// f[i][j] 表示i,j到0,0路径数
3
f := make([][]int, m)
4
for i := 0; i < m; i++ {
5
for j := 0; j < n; j++ {
6
if f[i] == nil {
7
f[i] = make([]int, n)
8
}
9
f[i][j] = 1
10
}
11
}
12
for i := 1; i < m; i++ {
13
for j := 1; j < n; j++ {
14
f[i][j] = f[i-1][j] + f[i][j-1]
15
}
16
}
17
return f[m-1][n-1]
18
}
Copied!
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径? 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
1
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
2
// f[i][j] = f[i-1][j] + f[i][j-1] 并检查障碍物
3
if obstacleGrid[0][0] == 1 {
4
return 0
5
}
6
m := len(obstacleGrid)
7
n := len(obstacleGrid[0])
8
f := make([][]int, m)
9
for i := 0; i < m; i++ {
10
for j := 0; j < n; j++ {
11
if f[i] == nil {
12
f[i] = make([]int, n)
13
}
14
f[i][j] = 1
15
}
16
}
17
for i := 1; i < m; i++ {
18
if obstacleGrid[i][0] == 1 || f[i-1][0] == 0 {
19
f[i][0] = 0
20
}
21
}
22
for j := 1; j < n; j++ {
23
if obstacleGrid[0][j] == 1 || f[0][j-1] == 0 {
24
f[0][j] = 0
25
}
26
}
27
for i := 1; i < m; i++ {
28
for j := 1; j < n; j++ {
29
if obstacleGrid[i][j] == 1 {
30
f[i][j] = 0
31
} else {
32
f[i][j] = f[i-1][j] + f[i][j-1]
33
}
34
}
35
}
36
return f[m-1][n-1]
37
}
Copied!

2、序列类型(40%)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
1
func climbStairs(n int) int {
2
// f[i] = f[i-1] + f[i-2]
3
if n == 1 || n == 0 {
4
return n
5
}
6
f := make([]int, n+1)
7
f[1] = 1
8
f[2] = 2
9
for i := 3; i <= n; i++ {
10
f[i] = f[i-1] + f[i-2]
11
}
12
return f[n]
13
}
Copied!

jump-game

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。
1
func canJump(nums []int) bool {
2
// 思路:看最后一跳
3
// 状态:f[i] 表示是否能从0跳到i
4
// 推导:f[i] = OR(f[j],j<i&&j能跳到i) 判断之前所有的点最后一跳是否能跳到当前点
5
// 初始化:f[0] = 0
6
// 结果: f[n-1]
7
if len(nums) == 0 {
8
return true
9
}
10
f := make([]bool, len(nums))
11
f[0] = true
12
for i := 1; i < len(nums); i++ {
13
for j := 0; j < i; j++ {
14
if f[j] == true && nums[j]+j >= i {
15
f[i] = true
16
}
17
}
18
}
19
return f[len(nums)-1]
20
}
Copied!
给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
1
// v1动态规划(其他语言超时参考v2)
2
func jump(nums []int) int {
3
// 状态:f[i] 表示从起点到当前位置最小次数
4
// 推导:f[i] = f[j],a[j]+j >=i,min(f[j]+1)
5
// 初始化:f[0] = 0
6
// 结果:f[n-1]
7
f := make([]int, len(nums))
8
f[0] = 0
9
for i := 1; i < len(nums); i++ {
10
// f[i] 最大值为i
11
f[i] = i
12
// 遍历之前结果取一个最小值+1
13
for j := 0; j < i; j++ {
14
if nums[j]+j >= i {
15
f[i] = min(f[j]+1,f[i])
16
}
17
}
18
}
19
return f[len(nums)-1]
20
}
21
func min(a, b int) int {
22
if a > b {
23
return b
24
}
25
return a
26
}
Copied!
1
// v2 动态规划+贪心优化
2
func jump(nums []int) int {
3
n:=len(nums)
4
f := make([]int, n)
5
f[0] = 0
6
for i := 1; i < n; i++ {
7
// 取第一个能跳到当前位置的点即可
8
// 因为跳跃次数的结果集是单调递增的,所以贪心思路是正确的
9
idx:=0
10
for idx<n&&idx+nums[idx]<i{
11
idx++
12
}
13
f[i]=f[idx]+1
14
}
15
return f[n-1]
16
}
Copied!
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回符合要求的最少分割次数。
1
func minCut(s string) int {
2
// state: f[i] "前i"个字符组成的子字符串需要最少几次cut(个数-1为索引)
3
// function: f[i] = MIN{f[j]+1}, j < i && [j+1 ~ i]这一段是一个回文串
4
// intialize: f[i] = i - 1 (f[0] = -1)
5
// answer: f[s.length()]
6
if len(s) == 0 || len(s) == 1 {
7
return 0
8
}
9
f := make([]int, len(s)+1)
10
f[0] = -1
11
f[1] = 0
12
for i := 1; i <= len(s); i++ {
13
f[i] = i - 1
14
for j := 0; j < i; j++ {
15
if isPalindrome(s, j, i-1) {
16
f[i] = min(f[i], f[j]+1)
17
}
18
}
19
}
20
return f[len(s)]
21
}
22
func min(a, b int) int {
23
if a > b {
24
return b
25
}
26
return a
27
}
28
func isPalindrome(s string, i, j int) bool {
29
for i < j {
30
if s[i] != s[j] {
31
return false
32
}
33
i++
34
j--
35
}
36
return true
37
}
Copied!
注意点
  • 判断回文字符串时,可以提前用动态规划算好,减少时间复杂度
给定一个无序的整数数组,找到其中最长上升子序列的长度。
1
func lengthOfLIS(nums []int) int {
2
// f[i] 表示从0开始到i结尾的最长序列长度
3
// f[i] = max(f[j])+1 ,a[j]<a[i]
4
// f[0...n-1] = 1
5
// max(f[0]...f[n-1])
6
if len(nums) == 0 || len(nums) == 1 {
7
return len(nums)
8
}
9
f := make([]int, len(nums))
10
f[0] = 1
11
for i := 1; i < len(nums); i++ {
12
f[i] = 1
13
for j := 0; j < i; j++ {
14
if nums[j] < nums[i] {
15
f[i] = max(f[i], f[j]+1)
16
}
17
}
18
}
19
result := f[0]
20
for i := 1; i < len(nums); i++ {
21
result = max(result, f[i])
22
}
23
return result
24
25
}
26
func max(a, b int) int {
27
if a > b {
28
return a
29
}
30
return b
31
}
Copied!
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
1
func wordBreak(s string, wordDict []string) bool {
2
// f[i] 表示前i个字符是否可以被切分
3
// f[i] = f[j] && s[j+1~i] in wordDict
4
// f[0] = true
5
// return f[len]
6
7
if len(s) == 0 {
8
return true
9
}
10
f := make([]bool, len(s)+1)
11
f[0] = true
12
max,dict := maxLen(wordDict)
13
for i := 1; i <= len(s); i++ {
14
l := 0
15
if i - max > 0 {
16
l = i - max
17
}
18
for j := l; j < i; j++ {
19
if f[j] && inDict(s[j:i],dict) {
20
f[i] = true
21
break
22
}
23
}
24
}
25
return f[len(s)]
26
}
27
28
29
30
func maxLen(wordDict []string) (int,map[string]bool) {
31
dict := make(map[string]bool)
32
max := 0
33
for _, v := range wordDict {
34
dict[v] = true
35
if len(v) > max {
36
max = len(v)
37
}
38
}
39
return max,dict
40
}
41
42
func inDict(s string,dict map[string]bool) bool {
43
_, ok := dict[s]
44
return ok
45
}
Copied!
小结
常见处理方式是给 0 位置占位,这样处理问题时一视同仁,初始化则在原来基础上 length+1,返回结果 f[n]
  • 状态可以为前 i 个
  • 初始化 length+1
  • 取值 index=i-1
  • 返回值:f[n]或者 f[m][n]

Two Sequences DP(40%)

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
1
func longestCommonSubsequence(a string, b string) int {
2
// dp[i][j] a前i个和b前j个字符最长公共子序列
3
// dp[m+1][n+1]
4
// ' a d c e
5
// ' 0 0 0 0 0
6
// a 0 1 1 1 1
7
// c 0 1 1 2 1
8
//
9
dp:=make([][]int,len(a)+1)
10
for i:=0;i<=len(a);i++ {
11
dp[i]=make([]int,len(b)+1)
12
}
13
for i:=1;i<=len(a);i++ {
14
for j:=1;j<=len(b);j++ {
15
// 相等取左上元素+1,否则取左或上的较大值
16
if a[i-1]==b[j-1] {
17
dp[i][j]=dp[i-1][j-1]+1
18
} else {
19
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
20
}
21
}
22
}
23
return dp[len(a)][len(b)]
24
}
25
func max(a,b int)int {
26
if a>b{
27
return a
28
}
29
return b
30
}
Copied!
注意点
  • go 切片初始化
1
dp:=make([][]int,len(a)+1)
2
for i:=0;i<=len(a);i++ {
3
dp[i]=make([]int,len(b)+1)
4
}
Copied!
  • 从 1 开始遍历到最大长度
  • 索引需要减一
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符
思路:和上题很类似,相等则不需要操作,否则取删除、插入、替换最小操作次数的值+1
1
func minDistance(word1 string, word2 string) int {
2
// dp[i][j] 表示a字符串的前i个字符编辑为b字符串的前j个字符最少需要多少次操作
3
// dp[i][j] = OR(dp[i-1][j-1],a[i]==b[j],min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1)
4
dp:=make([][]int,len(word1)+1)
5
for i:=0;i<len(dp);i++{
6
dp[i]=make([]int,len(word2)+1)
7
}
8
for i:=0;i<len(dp);i++{
9
dp[i][0]=i
10
}
11
for j:=0;j<len(dp[0]);j++{
12
dp[0][j]=j
13
}
14
for i:=1;i<=len(word1);i++{
15
for j:=1;j<=len(word2);j++{
16
// 相等则不需要操作
17
if word1[i-1]==word2[j-1] {
18
dp[i][j]=dp[i-1][j-1]
19
}else{ // 否则取删除、插入、替换最小操作次数的值+1
20
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1
21
}
22
}
23
}
24
return dp[len(word1)][len(word2)]
25
}
26
func min(a,b int)int{
27
if a>b{
28
return b
29
}
30
return a
31
}
Copied!
说明
另外一种做法:MAXLEN(a,b)-LCS(a,b)

零钱和背包(10%)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
思路:和其他 DP 不太一样,i 表示钱或者容量
1
func coinChange(coins []int, amount int) int {
2
// 状态 dp[i]表示金额为i时,组成的最小硬币个数
3
// 推导 dp[i] = min(dp[i-1], dp[i-2], dp[i-5])+1, 前提 i-coins[j] > 0
4
// 初始化为最大值 dp[i]=amount+1
5
// 返回值 dp[n] or dp[n]>amount =>-1
6
dp:=make([]int,amount+1)
7
for i:=0;i<=amount;i++{
8
dp[i]=amount+1
9
}
10
dp[0]=0
11
for i:=1;i<=amount;i++{
12
for j:=0;j<len(coins);j++{
13
if i-coins[j]>=0 {
14
dp[i]=min(dp[i],dp[i-coins[j]]+1)
15
}
16
}
17
}
18
if dp[amount] > amount {
19
return -1
20
}
21
return dp[amount]
22
23
}
24
func min(a,b int)int{
25
if a>b{
26
return b
27
}
28
return a
29
}
Copied!
注意
dp[i-a[j]] 决策 a[j]是否参与

backpack

在 n 个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为 m,每个物品的大小为 A[i]
1
func backPack (m int, A []int) int {
2
// write your code here
3
// f[i][j] 前i个物品,是否能装j
4
// f[i][j] =f[i-1][j] f[i-1][j-a[i] j>a[i]
5
// f[0][0]=true f[...][0]=true
6
// f[n][X]
7
f:=make([][]bool,len(A)+1)
8
for i:=0;i<=len(A);i++{
9
f[i]=make([]bool,m+1)
10
}
11
f[0][0]=true
12
for i:=1;i<=len(A);i++{
13
for j:=0;j<=m;j++{
14
f[i][j]=f[i-1][j]
15
if j-A[i-1]>=0 && f[i-1][j-A[i-1]]{
16
f[i][j]=true
17
}
18
}
19
}
20
for i:=m;i>=0;i--{
21
if f[len(A)][i] {
22
return i
23
}
24
}
25
return 0
26
}
Copied!
n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值. 问最多能装入背包的总价值是多大?
思路:f[i][j] 前 i 个物品,装入 j 背包 最大价值
1
func backPackII (m int, A []int, V []int) int {
2
// write your code here
3
// f[i][j] 前i个物品,装入j背包 最大价值
4
// f[i][j] =max(f[i-1][j] ,f[i-1][j-A[i]]+V[i]) 是否加入A[i]物品
5
// f[0][0]=0 f[0][...]=0 f[...][0]=0
6
f:=make([][]int,len(A)+1)
7
for i:=0;i<len(A)+1;i++{
8
f[i]=make([]int,m+1)
9
}
10
for i:=1;i<=len(A);i++{
11
for j:=0;j<=m;j++{
12
f[i][j]=f[i-1][j]
13
if j-A[i-1] >= 0{
14
f[i][j]=max(f[i-1][j],f[i-1][j-A[i-1]]+V[i-1])
15
}
16
}
17
}
18
return f[len(A)][m]
19
}
20
func max(a,b int)int{
21
if a>b{
22
return a
23
}
24
return b
25
}
Copied!

练习

Matrix DP (10%)
Sequence (40%)
Two Sequences DP (40%)
Backpack & Coin Change (10%)
最近更新 1yr ago