【动态规划1】一些基本问题的总结

vlambda
2020-04-29

【动态规划1】一些基本问题的总结

看了很多讲动态规划的文章，也刷了一些leetcode题目，但总是过一段时间就会忘记基本套路。所以想总结一下几个动态规划基本问题的解法。

动态规划的基本思路：（实际上不一定是对的，只是个人的理解，能够做出题目来就行）1.定义好dp数组，一定要弄清楚dp数组的含义，并根据问题不同维度状态的数量来决定dp数组的维度。比如“找零钱问题”中状态就只有总零钱数量M，因此dp[i]代表想要凑出i元钱，最少需要的硬币数量是dp[i]。在“求最长子序列”问题中，dp[i]表示数组的第i个位置之前（包括第i个位置）的最长子序列中元素的个数。在“0-1背包”问题中，dp[i][j]表示前i个物品在最大重量为j的限制下，所能装的最大价值量。2. 写出状态转移方程3.弄清楚初始状态，也就是递归的出口。下面来分析一下“找零钱”，“最长子序列”，“0-1背包”三个基本问题。

找零钱问题

问题描述：现在有硬币1，4，6三种，硬币数量不限制，问凑出11元所需要的最少硬币数量是多少？比如 1+4+6，或者1+4+4+1+1等等，都能凑出11元，问题要求的是凑出11元最少需要的硬币数量。

按照上面的基本思路，（1）我们要定义一个dp数组dp[i]，它表示凑出i元需要的最小硬币数量；（2）写出状态转移方程。假设现在已经知道了dp[i]之前的所有数据如dp[i-1],dp[i-2]等，下面我们来求dp[i]，此时情况如下：

for coin in coins:    dp[i] = min(dp[i], dp[i-coin]+1)

(3)弄清楚初始条件：当i=0时，dp[i]=0，当i<0时，也就是说，想凑齐一个负数金额，显然无解。

综上，代码如下：

def getMinCoins(coins: list, value: int) -> int: res = [float('INF')] * (value + 1) res[0] = 0 def dp(i): if i == 0: return 0 if i < 0: return -1 for coin in coins: if dp(i-coin) < 0: continue res[i] = min(res[i], dp(i-coin)+1) return res[i]    return dp(value)    if __name__ == '__main__': print(getMinCoins([1, 4, 6], 10))###########2

2. 最长递增子序列

问题描述：给定一个序列，求出它最长递增子序列中元素的个数。比如有一个序列是1，4 ，3，6，5， 8。那么它的最长递增子序列为 1468或者1358，元素个数均为4。

同样，按照基本思路：（1）弄清dp[i]的含义：dp[i]表示第i个元素（包括第i个元素）所具有的最长子序列的元素个数。（2）确定状态转移方程。假设dp[i]之前的数据dp[i-1],dp[i-2]等等全部已经知道，现在需要求dp[i]的值。这里，我们只需要找到在i之前，比i对应小的的所有元素j的dp[j]值，然后从中找到最大的那个dp[j]再加1即可。代码描述为：

for i, v in enumerate(list):    for j in list[0:i+1]:     if list[i] > list[j]:     dp[i] = dp[j] + 1

(3)确定初始条件，当i=1时对应的dp[i]（实际上是dp[0]）为1，当i<1时，无解

综上，代码如下：

def getMaxSeq(raw_seq: list) -> int: dp = [1] * len(raw_seq) for i, v in enumerate(raw_seq): for j, v1 in enumerate(raw_seq[0:i+1]): if v > v1: dp[i] = max(dp[i], dp[j]+1) return max(dp)

if __name__ == '__main__':    print(getMaxSeq([10,9,2,5,3,7,101,18,102]))########5

3.0-1背包问题

问题描述：现在有一个能装重量为W的背包一个，同时有n个物品，每个物品的重量分别为w，价值为v。现在求使背包能够装入的物品的价值量最大。

还是按照基本思路来分析。（1）与之前的内容不同，很明显，背包问题的限制状态有两个，一是物品的数量，二是背包的重量。所以dp[i][j]表示前i个物品在重量为j的背包限制下，能装入的最大价值量。（2）状态转移方程。假设dp[i-1][j-1]以及之前的数据全部已经知道，现在要求dp[i][j],有两种情况，第一，当第i个物品装入了背包中，dp[i][j] = dp[i-1][j-wt[i]] + val[i],第二，当第i个物品没有被装入背包中，dp[i][j] = dp[i-1][j]。（3）确定初始条件，dp[0][0..j] = 0,当没有物品时，价值为0，dp[0..i][0]=0，当背包容量为空时，价值为0.

综上，代码如下：

def getMaxBagValue(goods: list, wt: int) -> int: dp = [[0 for m in range(wt+1)]for k in range(len(goods)+1)] for i in range(1,len(goods)+1): for j in range(1, wt+1): if (j-goods[i-1][0]) < 0: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-goods[i-1][0]] + goods[i-1][1]) return dp[len(goods)][wt]

if __name__ == '__main__': print(getMaxBagValue([(2,4), (1,2), (3,3)], 4))#########6

关于python list的一点小坑：

dp = [[0]*2]*2#######[[0,0],[0,0]]注意里面的两个[0,0]放在内存中的同一位置，即dp[0][0]=1，则dp[1][0]也会变成1

vlambda博客
学习文章列表