数据结构与算法笔记 | 动态规划

动态规划算法的两大特征是递推公式和记忆数组。根据递推公式，大问题分解为重叠子问题（overlap sub-problem），子问题的解储存起来形成记忆。
动态规划算法的应用场景很多，具体构造也非常灵活。

一、动态规划与字符串结合

剑指Offer - 正则表达式匹配
这道题的输入是字符串str和匹配模式串pattern，字符串”aaa”可以匹配模式”a.a”和”abaca”，模式中的通配符只有 ‘.’ 和 ‘‘ 两种，和正则表达式标准所不同的是，’‘表示它前面的字符可以出现任意次，而不是匹配任意长度的字符。

假设布尔型 dp[m][n] 表示长度从1至m的字符串和长度从1至n的模式是否匹配，那么当递推到 dp[str.length][pattern.length]即为所求。

dp[1][1] 表示第一个字符是否匹配。
如果 pattern[2]=='.' || str[2] == pattern[2]，则 dp[2][2] = dp[1][1]，否则需要考虑通配符（比如字符串"0ab"与模式`”0ab”匹配，字符串“0ab”与模式“0a*c”`不匹配）
可以有如下几种情况考虑

1. 匹配掉双方第一个字符，如abc和a*bc匹配剩下：bc 和 bc
2. 匹配掉字符串的第一个字符，如aabc和a*bc匹配剩下：abc 和 a*bc
3. 匹配掉模式的两个字符，如bc和a*bc匹配剩下：bc和bc
   上述几种考虑编写代码段如下：

   if(pattern[2] == '.' || str[2] == pattern[2]) {
       dp[2][2] = dp[1][1]; // 第1种情况
   } else if(pattern[2] == '*') {
       if(dp[2][0] == true) {
           dp[2][2] = true;    // 第3种情况
       } else if(pattern[1]=='.' || pattern[1]==str[2]) {
           dp[2][2] = dp[1][2]; // 第2种情况
       }
   }

二、背包问题

背包问题的目标是将总价值尽可能高的物品塞到背包中，有以下几类常考问题：

01背包

有N件商品和容量为V的背包，第i(0<=i<N)件商品的体积是 c[i]，价值是 w[i]，每件商品最多只能用1次。求解将哪些商品放入背包中可在不超过背包容量的情况下使总价值达到最大。
我们设 dp[i][j] 为考虑前 i 件商品的情况下，容量不超过 j 的最大价值，则 dp[N][V] 即为所求。
初始值 dp[0][j]=0, dp[i][0]=0，
考虑第 i 件商品放或者不放，如果放，那么前i-1件商品的允许容量会减小c[i]，价值会加上第i件商品的价值w[i]，此时 dp[i][j] = dp[i-1][j-c[i]] + w[i]；如果不放，那么等价于前i-1件商品不超过容量j的最大价值，此时 dp[i][j] = dp[i-1][j]，故可以得到递推公式：
$$
dp[i][j] = max(dp[i-1][j-c[i]] + w[i], dp[i-1][j])
$$

注意01背包问题不能使用贪心思想求解，看下面的例子：

容量 V = 5
3件商品：
(体积=1, 价值=2) 单位体积价值=2
(体积=2, 价值=4) 单位体积价值=2
(体积=3, 价值=3) 单位体积价值=1

如果采用贪心思想，那么先放体积为1和2的物品，此时总价值达到6。剩余体积为2,放不下体积为3的商品了。
而我们知道最优解是放体积为2和3的商品，总价值为7。所以过度贪心，将会导致胸怀不够大，看不到全局最优解。

例题：分割等和子集

一些一维DP问题

丑数

定义丑数为质因子只包含2、3、5的数，给你一个正整数n，找出第n个丑数
通常认为，第一个丑数为1。

分析

除了1之外，第n个丑数只能是前面某个丑数乘2或乘3或乘5得到的结果。令p2,p3,p5储存前面某个丑数的下标，那么第i个丑数应为 dp[p2]*2,dp[p3]*3,dp[p5]*5 的最小值。
特征是假如第i个新丑数是第p2个丑数乘2得到的，则下标p2+1，第i+1个丑数为 dp[p2+1]*2,dp[p3]*3,dp[p5]*5 最小值；
第p3个丑数乘3得到的第i个丑数则下标p3+1，第i+1个丑数为 dp[p2]*2,dp[p3+1]*3,dp[p5]*5 最小值；
第p5个丑数乘5得到的则下标p5+1，第i+1个丑数为dp[p2]*2,dp[p3]*3,dp[p5+1]*5 最小值。

前缀和

前缀和数组细分有两种：
如果preSum[i]记录从0累加到i的和，那么计算数组第i到j个元素的累加和即为 preSum[j]-preSum[i]+arr[i]
如果preSum[i]（i>0）记录从下标0累加到下标i-1的和，preSum[0]=0，那么计算数组下标i到j的元素累加和即为 preSum[j+1]-preSum[i]

例题：所有奇数长度子数组的和

利用前缀和还可以构造差分数组，例题：航班预订统计