# mutoe/blog

Fetching contributors…
Cannot retrieve contributors at this time
550 lines (394 sloc) 16.1 KB
title date categories tags mathjax

2019-02-25 13:57:14 -0800

 Dynamic Programming
true

# 怎么求解动态规划问题

1. 如何用最少的硬币凑够0元?
2. 如何用最少的硬币凑够1元?
3. 如何用最少的硬币凑够2元?
4. ...
5. 如何用最少的硬币凑够11元?

## “状态”是什么

“状态”用来描述该问题的子问题的解。

$$d(0)=0$$

$$d(1)=d(1-1)+1=d(0)+1=0+1=1$$

$$d(2)=d(2-1)+1=d(1)+1=1+1=2$$

1. 拿起1元硬币

$$d(3)=d(3-1)+1=d(2)+1=2+1=3$$

1. 拿起3元硬币

$$d(3)=d(3-3)+1=d(0)+1=0+1=1$$

$$d(3)=\min\{d(3-1)+1, d(3-3)+1\}$$

$$d(3)=\min\{d(3-1)+1, d(3-3)+1\}$$

$$d(i)=\min\{d(i-v_j)+1\}$$

$i$ $j$ $v_j$ ($\min\{d(i-v_j)\}$)
0 0 -
1 1 1 (0)
2 2 1 (1)
3 1 3 (0)
4 2 1 (3)
5 1 5 (0)
6 2 3 (3)
7 3 1 (6)
8 2 3 (5)
9 3 1 (8)
10 2 5 (5)
11 3 1 (10)

$$d(11)=d(10)+1=d(5)+1+1=d(0)+1+1+1=3$$

BB 这么多没用， Show your code !

# 代码实现

Leetcode 322. Coin Change

## Golang

### main

// CoinChange: coins 硬币, amount 期望的金额, 返回最少需要的硬币数量，如果不可解返回-1
func CoinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 0

for i := 1; i <= amount; i++ {
dp[i] = amount + 1
for _, coin := range coins {
if coin <= i && dp[i-coin] != -1 && dp[i-coin]+1 < dp[i] {
dp[i] = dp[i-coin] + 1
}
}
if dp[i] > amount {
dp[i] = -1
}
}

return dp[amount]
}

### unit test

import "testing"

func TestCoinCharge(t *testing.T) {
type args struct {
coins  []int
amount int
}
tests := []struct {
name string
args args
want int
}{
{"[2] => 3", args{[]int{2}, 3}, -1},
{"[2] => 4", args{[]int{2}, 4}, 2},
{"[1,2,5] => 11", args{[]int{1, 2, 5}, 11}, 3},
{"[1,3,5] => 11", args{[]int{1, 3, 5}, 11}, 3},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := CoinCharge(tt.args.coins, tt.args.amount); got != tt.want {
t.Errorf("CoinCharge() = %v, want %v", got, tt.want)
}
})
}
}


### Leetcode result

Runtime: 8 ms, faster than 99.26% of Go online submissions for Coin Change.


# 初级 DP 问题

Leetcode 300. Longest Increasing Subsequence
LIS: 有一个序列有 N 个数，A[1],A[2],...,A[N]. 求出其最长递增子序列的长度。

5, 3, 4, 8, 6, 7


$d(1)=1$ (5) // 5前面没有比它小的 $d(1)=1$

$d(2)=1$ (3) // 3前面没有比它小的 $d(2)=1$

$d(3)=2$ (3 4) // 4前面有1个比它小的，所以 $d(3)=d(2)+1=2$

$d(4)=3$ (3 4 8) // 8前面比他小的有3个数, 所以 $d(4)=\max\{d(1), d(2), d(3)\}+1=3$

$d(5)=3$ (3 4 6) // 6前面比他小的有3个数，所以 $d(5)=\max\{d(1), d(2), d(3)\}+1=3$

$d(6)=4$ (3 4 6 7) // 7前面比他小的有4个数，所以 $d(6)=\max\{d(1), d(2), d(4), d(5)\}+1=4$

$$d(i)= \max\{1, d(j)+1\} (j \lt i, A[j] \lt A[i])$$

## Golang 实现

Leetcode 300. Longest Increasing Subsequence

### main $O(n^2)$

func lengthOfLIS(nums []int) int {
dp := make([]int, len(nums))
maxLen := 0

for i, num := range nums {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[j] < num && dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
}
}
if dp[i] > maxLen {
maxLen = dp[i]
}
}

return maxLen
}

### unit test

import "testing"

func Test_lengthOfLIS(t *testing.T) {
type args struct {
nums []int
}
tests := []struct {
name string
args args
want int
}{
{"4", args{[]int{10, 9, 2, 5, 3, 7, 101, 18}}, 4},
{"4", args{[]int{10, 9, 2, 2, 5, 3, 7, 101, 18}}, 4},
{"6", args{[]int{1, 3, 6, 7, 9, 4, 10, 5, 6}}, 6},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := lengthOfLIS(tt.args.nums); got != tt.want {
t.Errorf("lengthOfLIS() = %v, want %v", got, tt.want)
}
})
}
}

### Leetcode result

Runtime: 8 ms, faster than 69.34% of Go online submissions for Longest Increasing Subsequence.
Memory Usage: 2.3 MB, less than 95.45% of Go online submissions for Longest Increasing Subsequence.


# 中级 DP 问题

$$S[i][j] = A[i][j] + \max\{S[i-1][j], S[i][j-1]\}$$

$$S[1][1] = A[1][1] + \max\{S[1][0], S[0][1]\}$$

$$S[1][0] = A[1][0] + S[0][0] = 4 + 1 = 5$$ $$S[0][1] = A[0][1] + S[0][0] = 2 + 1 = 3$$

$$S[1][1] = A[1][1] + S[1][0] = 5 + 5 = 10$$

## Golang 实现

Leetcode 64. Minimum Path Sum

### main

package main

func min(x, y int) int {
if x > y {
return y
}
return x
}

func minPathSum(grid [][]int) int {
row := len(grid)
col := len(grid[0])
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if i == 0 && j == 0 {
continue
} else if i == 0 {
grid[i][j] += grid[i][j-1]
} else if j == 0 {
grid[i][j] += grid[i-1][j]
} else {
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
}
}
}
return grid[row-1][col-1]
}

### unit test

import "testing"

func Test_minPathSum(t *testing.T) {
type args struct {
grid [][]int
}
tests := []struct {
name string
args args
want int
}{
{"7", args{[][]int{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1},
}}, 7},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := minPathSum(tt.args.grid); got != tt.want {
t.Errorf("minPathSum() = %v, want %v", got, tt.want)
}
})
}
}

### Leetcode result

Runtime: 8 ms, faster than 100.00% of Go online submissions for Minimum Path Sum.
Memory Usage: 3.9 MB, less than 95.45% of Go online submissions for Minimum Path Sum.


# 中高级 DP 问题

• 如果限定每种物品只能选择 0 个或者 1 个，则问题称为 0-1背包问题，可表示为 $\text{最大化:} \sum_{j=1}^n p_j x_j$ $\text{受限于:} \sum_{j=1}^n w_j x_j \leq W, x_j \in \{0, 1\}$

• 如果限定物品 $j$ 最多只能选择 $b_j$ 个，则问题称为有界背包问题，可表示为 $最大化: \sum_{j=1}^n p_j x_j$ $受限于: \sum_{j=1}^n w_j x_j \leq W, x_j \in \{0, 1, ..., b_j\}$

• 如果不限定每种物品的数量，则问题称为无界背包问题

1. 5 个物品放入背包容量为 0 的最优解
2. 5 个物品放入背包容量为 1 的最优解
3. 5 个物品放入背包容量为 2 的最优解
4. ...
5. 5 个物品放入背包容量为 13 的最优解
• 情况 1. 显然，背包容量为 0 时没有东西能放入，即 $d(5, 0) = 0$，以此类推 $d(i, 0) = 0, i \in \{0, 1, ..., N \}$

• 情况 2. 背包容量为 1 时也没有东西能放入，因为 $W_i < j = 1, i \in \{0,4\}$ 也不存在

• 当 $j=2$ 时，存在 $W_i < j = 2$，此时 $i-1=2$，为 [2, 3] 这个物品，即 $d(5, 2) = V_3 = 3$

• 当 $j=3$ 时，同上， $d(5, 3) = d(5, 2) = 3$

• 当 $j=4$ 时，情况稍微复杂一点，我们可以再次拆解这个子问题

1. 前 0 个物品放入背包容量为 4 的最优解
2. 前 1 个物品放入背包容量为 4 的最优解
3. ...
4. 前 5 个物品放入背包容量为 4 的最优解
• 情况 i. 显然，没有物品放入时，价值也为0，即 $d(0, 4) = 0$, 以此类推 $d(0, j) = 0, j \in \{0, 1, ..., W\}$

• 情况 ii. 也不存在 $W_i < j = 4, i \in \{0, 1\}$，故 $d(1, 4) = 0$

• 当 $i=2$ 时，存在 $W_i < j = 4, i \in \{0, 1, 2\}$，此时 $i-1 = 1$，即 $d(2, 4) = V_1 = 3$

• $i=3$ 时，同上，$d(3, 4) = d(2, 4) = 3$

• $i=4$ 时，我们考虑是否要将 $i-1=3$ 的物品放入背包中 如果不放入 $d(4, 4) = d(3, 4) = 3$ 如果放入则 $d(4, 4) = d(3, j - W_{i-1}) + V_{i-1} = d(3, 2) + 3 = 0 + 3 = 3$

对于这种情况的解释，如我我们考虑前 i 个物品的最优解，则就是在求是否要将第 $i-1$ 个物品放入背包中取得的最优解

于是 $d(4,4) = \max\{d(3, 4), d(3, 2) + 3\} = \max\{3, 3\} = 3$

$$d(i, j) = \begin{cases} 0, & \text{if i=0 or j=0} \\ d(i-1, j), & \text{if d(i-1, j) > d(i-1, j-W_{i-1}) + V_{i-1}} \\ d(i-1, j-W_{i-1}) + V_{i-1}, & \text{otherwise} \\ \end{cases}$$

## Golang 实现

### main

func backpack(w, v []int, W int) int {
size := len(w)
dp := make([][]int, W+1)
for j := 0; j <= W; j++ {
dp[j] = make([]int, size+1)
}

for j := 1; j <= W; j++ {
for i := 1; i <= size; i++ {
weight := w[i-1]
if weight > j {
dp[j][i] = dp[j][i-1]
continue
}
dp[j][i] = dp[j-weight][i-1] + v[i-1]
if dp[j][i-1] > dp[j][i] {
dp[j][i] = dp[j][i-1]
}
}
}

return dp[W][size]
}

### unit test

import "testing"

func Test_backpack(t *testing.T) {
type args struct {
w []int
v []int
W int
}
tests := []struct {
name string
args args
want int
}{
{"13", args{
[]int{5, 4, 7, 2, 6},
[]int{12, 3, 10, 3, 6},
13}, 22},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := backpack(tt.args.w, tt.args.v, tt.args.W); got != tt.want {
t.Errorf("backpack() = %v, want %v", got, tt.want)
}
})
}
}

# 参考链接

You can’t perform that action at this time.