Dynamic Programming

背包问题

有个背包，可以装4磅的东西。怎样装以下的商品，可以使得背包里的东西价值最高？

音响：3000美元，4磅

笔记本电脑：2000美元，3磅

吉他：1500美元，1磅

简单算法

尝试所有可能的组合，并找出价值最高的组合

什么也不装：0美元

吉他：1500美元

笔记本电脑：2000美元

音响：3000美元

吉他+笔记本电脑：3500美元

~~吉他+音响：超重~~

~~笔记本电脑+音响：超重~~

~~吉他+笔记本电脑+音响：超重~~
所以，价值最高的装法是：吉他+笔记本电脑

若涉及$n$个商品，则需计算 $2^n$ 个可能的集合，运行时间为 $O(2^n)$

动态规划

考虑背包问题：

有$n$个商品

背包最多可装重量为$m$的物品

将背包划分为$n行\times m列$的网格：

第$i$行表示将尝试将第$i$个商品装入背包

第$j$列表示背包的容量为$j$

$(i,j)$位置的网格表示只考虑前$i$个物品，容量为$j$的背包最多可容量的物品的总价值

	1	2	3	4
吉他	$1500	$1500	$1500	$1500
音响
笔记本电脑
只考虑1磅的吉他，1~4容量的背包最多可容纳1500美元的物品（只能容纳吉他）。

第$i$行、第$j$列单元格的价值为：
$$cell[i][j] = \max{cell[i-1][j], 当前商品的价值+cell[i-1][j-当前商品的重量]}$$
即，考虑下面二者中较大的那个：

上一个单元格的值
当前商品的价值+剩余空间的价值

背包问题的约束不一定是容量，也可能是：

有限的时间
有限的金钱

小结：

问题可分解为离散子问题时，可使用动态规划来解决

最长公共子串

考虑两个字符串的最长公共子串：

persecute 迫害
prosecute 起诉

	P	E	R	S	E	C	U	T	E
P	1	0	0	0	0	0	0	0	0
R	0	0	1	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0
S	0	0	0	1	0	0	0	0	0
E	0	1	0	0	2	0	0	0	1
C	0	0	0	0	0	3	0	0	0
U	0	0	0	0	0	0	4	0	0
T	0	0	0	0	0	0	0	5	0
E	0	1	0	0	1	0	0	0	6

$(i,j)$位置的网格值$cell[i][j]$为

如果第$i$行的字符和第$j$行的字符不相同，则为零
$$cell[i][j]=0$$
如果第$i$行的字符和第$j$行的字符相同，则为左上角的值加1
$$cell[i][j]=cell[i-1][j-1]+1$$

最长公共子串的长度为网格中的最大值。

上例为6——“secute”

字符串长度并不要求一致

查找“fish”和“flash”的最长公共子串

	F	S	H
F	1	0	0
I	0	0	0
S	0	1	0
H	0	0	2

最长公共子串（“sh”）长度为2

最长公共子序列

考虑两个字符串的最长公共子序列：

persecute 迫害
prosecute 起诉

	P	E	R	S	E	C	U	T	E
P	1	1	1	1	1	1	1	1	1
R	1	1	2	2	2	2	2	2	2
O	1	1	2	2	2	2	2	2	2
S	1	1	2	3	3	3	3	3	3
E	1	2	2	3	4	4	4	4	4
C	1	2	2	3	4	5	5	5	5
U	1	2	2	3	4	5	6	6	6
T	1	2	2	3	3	5	6	7	7
E	1	2	2	3	4	5	6	7	8

$(i,j)$位置的网格值$cell[i][j]$为

如果第$i$行的字符和第$j$行的字符不相同，则为上方和左方较大的那个网格值
$$cell[i][j]=max{cell[i-1][j], cell[i][j-1]}$$
如果第$i$行的字符和第$j$行的字符相同，则为左上角的值加1
$$cell[i][j]=cell[i-1][j-1]+1$$

最长公共子序列的长度为网格中的最大值。

上例为8——“prsecute”

字符串长度并不要求一致

查找“fish”和“flash”的最长公共子序列

	F	L	A	S	H
F	1	1	1	1	1
I	1	1	1	1	1
S	1	1	1	2	2
H	1	1	1	2	3

最长公共子序列（“fsh”）长度为3

最长递增子序列

计算序列nums=$[10,9,2,5,3,7,101,18]$中的最长递增子序列的长度

使用长度为序列长度的数组dp，其中dp$[i]$记录以nums$[i]$为结尾的最长递增子序列的长度。

dp的初始值都为1
nums[2]=9
nums[2] < nums[1]，所以dp[2]=1不变
nums[3]=2
nums[3] < nums[1] ，所以 dp[3]=1 不变
nums[3] < nums[2] ，所以 dp[3]=1 不变
nums[4]=5
nums[4] < nums[1] ，所以 dp[4]=1 不变
nums[4] < nums[2] ，所以 dp[4]=1 不变
nums[4] > nums[3] ，所以 dp[4]=$\max{$dp[4], dp[3]+1$}$=2
nums[5]=3
nums[5] < nums[1] ，所以 dp[5]=1 不变
nums[5] < nums[2] ，所以 dp[5]=1 不变
nums[5] > nums[3] ，所以 dp[5]=$\max{$dp[5], dp[3]+1$}$=2
nums[5] > nums[4] ，所以 dp[5]=2 不变
nums[6]=7
nums[6] < nums[1] ，所以 dp[6]=1 不变
nums[6] < nums[2] ，所以 dp[6]=1 不变
nums[6] > nums[3] ，所以 dp[6]=$\max{$dp[6], dp[3]+1$}$=2
nums[6] > nums[4] ，所以 dp[6]=$\max{$dp[6], dp[4]+1$}$=3
nums[6] > nums[5] ，所以 dp[6]=$\max{$dp[6], dp[5]+1$}$=3
nums[7]=101
nums[7] > nums[1] ，所以 dp[7]=$\max{$dp[7], dp[1]+1$}$=2
nums[7] > nums[2] ，所以 dp[7]=$\max{$dp[7], dp[2]+1$}$=2
nums[7] > nums[3] ，所以 dp[7]=$\max{$dp[7], dp[3]+1$}$=2
nums[7] > nums[4] ，所以 dp[7]=$\max{$dp[7], dp[4]+1$}$=3
nums[7] > nums[5] ，所以 dp[7]=$\max{$dp[7], dp[5]+1$}$=3
nums[7] > nums[6] ，所以 dp[7]=$\max{$dp[7], dp[6]+1$}$=4
nums[8]=18
nums[8] > nums[1] ，所以 dp[8]=$\max{$dp[8], dp[1]+1$}$=2
nums[8] > nums[2] ，所以 dp[8]=$\max{$dp[8], dp[2]+1$}$=2
nums[8] > nums[3] ，所以 dp[8]=$\max{$dp[8], dp[3]+1$}$=2
nums[8] > nums[4] ，所以 dp[8]=$\max{$dp[8], dp[4]+1$}$=3
nums[8] > nums[5] ，所以 dp[8]=$\max{$dp[8], dp[5]+1$}$=3
nums[8] > nums[6] ，所以 dp[8]=$\max{$dp[8], dp[6]+1$}$=4
nums[8] < nums[7] ，所以 dp[8]=4 不变

序列nums=[10,9,2,5,3,7,101,18]中的最长递增子序列长度为dp[8]=4
最长递增子序列为$[2, 5, 7, 101]$

在线编程：Leetcode-300. Longest Increasing Subsequence

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)  ## 列表长度
        if n == 0:
            return 0
        dp = [1 for i in range(n)]  ## 初始值都是1
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

Skye

Algorithms | 动态规划