背景知识
关键词
- 边界条件
- 递归（自顶向下）
- 缓存（一维数组、二位数组、滚动数组、etc.）
- 递推（自底向上）
定义
- 本质：递归
- 原问题（N）-> 子问题（N-1…）-> 原问题（N）
- 最优子结构
- 重叠子问题
问题共性
基本步骤
- 设计暴力算法，找到冗余
- 设计并存储状态（一维、二维、三维数组，甚至Map）
- 递归式（状态转移方程）
- 自底向上计算最优解（编程方式）
问题
背包问题
假设你是个小偷，背着一个可装 4磅东西的背包。 你可盗窃的商品有如下3件。
- 音响 3000美元 4磅
- 笔记本电脑 2000美元 3磅
- 吉他 1500美元 1磅
为了让盗窃的商品价值最高，你该选择哪些商品？
分析
动态规划先解决子问题，再逐 步解决大问题。 对于背包问题，先解决小背包（子背包）问题，再逐步解决原来的问题。
|
1 |
2 |
3 |
4 |
| 吉他G*1 |
1500 G |
1500 G |
1500 G |
1500 G |
| 音响S*1 |
1500 G |
1500 G |
1500 G |
3000 S |
| 笔记本L*1 |
1500 G |
1500 G |
2000 L |
3500 GL |
备注：各行为可选择的商品，各列为不同容量（1-4磅）的背包，交点代表背包为某个容量且可偷的物品为以上几种时的 偷窃方案 和 总价值
1
| cell[i][j] = max(cell[i-1][j], 当前物品的价值 + cell[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
35
|
"""
Created on Mon Jul 15 00:33:44 2019
@author: liyv1
"""
goods = ['G','S','L']
price_obj = {'G':1500, 'S':3000, 'L':2000}
weight_obj = {'G':1, 'S':4, 'L':3}
price = [1500, 3000, 2000]
weight = [1, 4, 3]
vol = 4
dp = [[0 for j in range(0, vol + 1)] for i in range(0, len(goods) + 1)]
for i in range(1, len(goods) + 1):
for j in range(1, vol + 1):
if j - weight[i - 1] >= 0:
dp[i][j] = max(dp[i - 1][j], price[i - 1] + dp[i - 1][j - weight[i - 1]])
else:
dp[i][j] = dp[i - 1][j]
print(dp)
i = len(goods)
j = vol
res = [];
while i > 0 and j > 0:
if dp[i][j] > dp[i - 1][j]:
res.append(price[i - 1])
j = j - weight[i - 1]
i = i - 1
print(res)
|
输出结果为：
1
2
3
4
5
6
7
| [
[0, 0, 0, 0, 0],
[0, 1500, 1500, 1500, 1500],
[0, 1500, 1500, 1500, 3000],
[0, 1500, 1500, 2000, 3500]
]
[2000, 1500]
|
项目实际问题
A 为原字符串，B 为更改后的字符串，求解 B 相比 A 做了哪些改动，标注新增、删除以及不变的部分。
解法
【php text diff的实现, 基于最长公共子序列 】用到了动态规划进行求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| <?php
namespace TextDiff;
define("PATH_TOP", 1);
define("PATH_TOPLEFT", 2);
define("PATH_LEFT", 3);
define("PATH_NONE", 0);
class DPModel {
public $value;
public $path;
public function __construct($v, $p)
{
$this->value = $v;
$this->path = $p;
}
}
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| <?php
namespace TextDiff;
class TextDiff {
public function diff(string $a, string $b, bool $html = false)
{
$alen = mb_strlen($a, 'UTF-8');
$blen = mb_strlen($b, 'UTF-8');
$dp = new \SplFixedArray($alen+1);
for ($i = 0; $i < $alen+1; $i++) {
$dp[$i] = new \SplFixedArray($blen+1);
if ($i == 0) {
for ($j = 0; $j < $blen + 1; $j++) {
$dp[$i][$j] = new DPModel(0, PATH_NONE);
}
} else {
$dp[$i][0] = new DPModel(0, PATH_NONE);
}
}
for($i = 1; $i < $alen+1; $i++) {
for($j = 1; $j < $blen+1; $j++) {
$aChar = mb_substr($a, $i-1, 1, 'UTF-8');
$bChar = mb_substr($b, $j-1, 1, 'UTF-8');
if ($aChar === $bChar) {
$dp[$i][$j] = new DPModel($dp[$i-1][$j-1]->value + 1, PATH_TOPLEFT);
} else {
if ($dp[$i-1][$j]->value >= $dp[$i][$j-1]->value) {
$dp[$i][$j] = new DPModel($dp[$i-1][$j]->value, PATH_TOP);
} else {
$dp[$i][$j] = new DPModel($dp[$i][$j-1]->value, PATH_LEFT);
}
}
}
}
$i = $alen;
$j = $blen;
$res = [];
while($i > 0 && $j > 0) {
switch ($dp[$i][$j]->path) {
case PATH_TOP:
$res[] = [mb_substr($a, $i-1, 1, 'UTF-8'), 'd'];
$i--;
break;
case PATH_TOPLEFT:
$res[] = [mb_substr($a, $i-1, 1, 'UTF-8'), 'u'];
$i--;
$j--;
break;
case PATH_LEFT:
$res[] = [mb_substr($b, $j-1, 1, 'UTF-8'), 'a'];
$j--;
break;
}
}
$res = array_reverse($res);
if ($html) {
return $this->toHtml($res);
} else {
return $res;
}
}
public function toHtml($res) {
$str = '';
foreach($res as $item) {
if ($item[1] == 'u') {
$str .= '<span class="text-unchange">'.$item[0].'</span>';
} else if ($item[1] == 'd') {
$str .= '<S class="text-delete">'.$item[0].'</S>';
} else {
$str .= '<B class="text-new">'.$item[0].'</B>';
}
}
return $str;
}
}
|
分析
作者用 ($alen + 1) * ($blen + 1) 的二维数组 $dp 来缓存 当前坐标最长公共子序列的长度 和 当前坐标的来源路径
字符串 A : “湖山秋远色变”
字符串 B : “湖光秋色”
|
0 |
1 |
2 |
3 |
4 |
| 0 |
0,- |
0,- |
0,- |
0,- |
0,- |
| 1 |
0,- |
1,↖ |
1,← |
1,← |
1,← |
| 2 |
0,- |
1,↑ |
1,↑ |
1,↑ |
1,↑ |
| 3 |
0,- |
1,↑ |
1,↑ |
2,↖ |
2,← |
| 4 |
0,- |
1,↑ |
1,↑ |
2,↑ |
2,↑ |
| 5 |
0,- |
1,↑ |
1,↑ |
2,↑ |
3,↖ |
| 6 |
0,- |
1,↑ |
1,↑ |
2,↑ |
3,↑ |
$dp[1][1] 记录了字符串 “湖” 和 “湖” 的 最长公共子序列的长度
$dp[6][4]记录了字符串 “湖山秋远色变” 和 “湖光秋色” 的 最长公共子序列的长度
从字符串A 变化到字符串B
箭头 ↑ 代表删除 A 字符串的字符
箭头← 代表新增 B 字符串的字符
箭头↖ 代表 无操作
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 0 |
0,- |
0,- |
0,- |
0,- |
0,- |
0,- |
0,- |
| 1 |
0,- |
1,↖ |
1,← |
1,← |
1,← |
1,← |
1,← |
| 2 |
0,- |
1,↑ |
1,↑ |
1,↑ |
1,↑ |
1,↑ |
1,↑ |
| 3 |
0,- |
1,↑ |
1,↑ |
2,↖ |
2,← |
2,← |
2,← |
| 4 |
0,- |
1,↑ |
1,↑ |
2,↑ |
2,↑ |
3,↖ |
3,← |
$dp[1][1] 记录了字符串 “湖” 和 “湖” 的 最长公共子序列的长度
$dp[4][6]记录了字符串 “湖山秋远色变” 和 “湖光秋色” 的 最长公共子序列的长度
从字符串A变化到字符串B
箭头 ↑ 代表新增 B 字符串的字符
箭头← 代表删除 A 字符串的字符
箭头↖ 代表 无操作
拓展资料
简析Myers