其实早就想总结一下看完讲解之后对dp的总结了。总体感受就是，dp的题做起来很神奇，比较有意思，而且经常让人感到惊奇“还可以这样看问题!”。不过看多了之后发现规律性也挺强的。即便如此，作为出来至少是medium经常是hard的类型，dp要完全掌握还是需要大量练习，并且经常想这个问题。

虽然我看了不少，而且包括超级经典的题目, e.g. Edit Distance, Regular Expression Matching, 各种背包问题 etc. 经常出现: 这些题隔一天我就不会做了… 还是没有完全理解。不过还是要尽量可能去理解。

正文部分:

空间优化:

对于网格的dp，如果f[i][j]只依赖本行的f[i][x]和上一行的f[i-1][y],那么可以采用滚动数组压缩空间. 空间复杂度为O(n)而不是O(m*n)

  1. Minimum Path Sum: 如果要打印path, 关键: 记录每一次是从left还是up的方向来的; 最后的path是从A[m-1][n-1]倒着得到的; 然后再reverse打印出来;
  2. Longest Increasing Subsequence(经典中的经典, 需要闭着眼睛都能写出来); dp[i][j]记录到grid[i][j]的位置的LIS长度;
  3. Bomb Enemy: 四个方向; e.g. 从上面来的方向: if(i>0) up[i][j] = up[i-1][j]+1;
  4. Longest Increasing Subsequence奇淫技巧: O(NlogN)

异或: 不进位的加法: 1^1 = 0;

Counting Bits:

  1. brute-force:这个数不断mod2, floor(i/2); 直到最后为0: O(NlogN);
  2. dp; 每个二进制数看最后一位是0/1, 再看去掉最后一位之后剩下的二进制有多少个1;
  3. >>:右移相当于除2往下找floor();
  4. <<:左移相当于乘2;
  5. 另外, i%2是很慢的, i & 1有相同的作用, 但是位操作比mod快很多;

坐标型&&序列型dp区别:

  1. 坐标型dp: f[i]表示以ai为结尾的某种性质
  2. 序列型dp: f[i]下标i表示前i个元素a[0], ...a[i-1]的某种性质
  3. 序列型dp这样，是因为初始化的时候f[0]表示前0个，所以就是空序列,这样的话初始化条件很简单

最长序列型dp: 本质上是坐标型dp

序列+状态型dp:

  1. when: 当思考dp到最后一步时，这一步依赖前一步的某种状态
  2. 初始化时，f[0]代表前0个元素/前0天的状态–与坐标型dp区别
  3. 计算时, f[i]代表前i 个元素, i.e. 元素0- (i-1)的某种性质

划分型dp:

  1. subset;
  2. game theory;
  3. backpack: 背包问题;

常见: 给定长度为K的序列或string，要求划分成若干段;

  • 段数不限，或者指定K段; 段数不限的时候就不用记录段数， 指定K段需要开一维记录段数;
  • 每一段满足一定的性质;

approach:

  • 类似序列型dp, 但是通常要加上段数信息; e.g. best time to buy sell stocks;
  • 一般用f[i][j]记录前i个元素(元素0 ~ i-1分成j段的性质, e.g. minCost;

只要是求min/max: int[] f = new int[n+1];
如果是划分成K段, etc. 需要记录K的状态的; 需要开一维记录; int[][] f

划分型dp一定是有group/partition, 并且有”连续的”这个意思

博弈:

  1. 只有博弈的dp是从第1步开始，其他的dp都是从最后一步开始分析;
  2. 这是因为dp的本质是找子问题，把问题的规模缩小，而博弈中最复杂的是第一步，每走一步问题规模都在缩小
  3. 状态一般都是用true/false表示“必胜／必败”

e.g. Coins in a Line;
f[n]–> f[n-1], f[n-2]状态的转移，都看先手的必胜/必败状态，由对方的必胜必败状态得到自己的必胜必败状态.

背包问题 (也是划分型dp)

  1. 背包问题，一定有一维跟总承重M相关: i.e. 开一个数组大小是M+1, 这个增加的时候表示当前的重量是多少; 如果没有就错了;
  2. lintcode: backpack
  3. f[i][j] 表示前i个物品能不能拼出重量为j；
    上面说了那么多，实际上背包问题几乎都是两维的，一维表示“到前i个物品”，另一维表示M那一维逐渐增加对应的值

一定有一维对应总承重M

要求不超过target的时候能拼出的最大重量: f记录前i个物品能拼出哪些重量;

前i个物品能拼出的重量:

  • 前i－1个物品能拼出的重量;
  • 前i－1个物品能拼出的重量 ＋ 第i个物品重量A[i-1]

f[i][j]并不一定就是true/false, 有可能表达别的含义，e.g. 有多少种方式拼出当前w, etc.

背包总结:

Backpack可行性背包(f: boolean):

  • 题目要求最多装多少重量 （能不能得到这个重量)
  • 记录前i个物品能不能拼出重量w (如果不能达到w只记录一维能得到的最大值, 答案会错)

Backpack V, Backpack VI: 计数型背包(f: int):

  • 题目要求有多少种方式装出重量
  • Backpack V: 记录前i个物品有多少种方式拼出重量w
  • Backpack VI: 记录有多少种方式拼出重量w

关键点: 最后一步:

  • 没有顺序: 最后一步背包的物品是哪个
  • 有顺序: 最后一个物品有没有进背包(前i个物品…)

附: 打印路径;

  1. 打出最优解的一种路径: dp用pi数组;
  2. 打出所有路径: dfs

lintcode的背包的题目: 下面3种分别对应存在性，最值，可行性的种类;

  1. backpack 1: f[i][j]表示前i个物品拼出重量为j是不是可能: or
  2. backpack 2: f[i][j]表示前i个物品拼出重量为j时能获得的max价值, -1就表示不能拼出重量为j: max; 此时的状态转移方程不能用f[i][j], 因为这个-1不仅仅是值，还是表示这个并不能拼出来，所以不能用
  3. backpack 5: f[i][j]表示前i个物品拼出重量为j有多少种可能: add
  4. backpack 6: 每次物品可以用无穷多次: e.g. 可以用第1个，再第2个，再第1个… 所以不能考虑顺序了, i.e. 前i个...不能用了, 所以考虑最后一个物品是谁(参见上面的关键点:最后一步), 而不是(按顺序)看最后一个物品有没有进背包
  5. backpack 3: 每个物品可以用无穷多次求最大价值; 无穷多次, 但是并不是求有多少种, 所以物品的顺序还存在, (注: “用无穷多次”和有无顺序并没有直接对应关系; 有无顺序/能不能用“前i个这种思路”是和“是不是求种类”有对应关系, 因为如果是求种类，可以前后来回取前后的物品，那么才没有顺序)

顺序存在，就看最后一个物品进没进背包;

顺序不存在, 就看最后一个物品是谁

  1. backpack 2: f[i][w]表示前i个物品拼出重量w时的最大总价值(-1表示不能拼出w);
  2. backpack 2: f[i][w] = max(f[i-1][w], f[i-1][w-A[i-1]] + V[i-1]);
  3. backpack 3: f[i][w]表示前i种物品拼出重量w时的最大总价值(-1表示不能拼出w);
  4. backpack 3: f[i][w]= max,k>=0 { f[i-1][w - k* A[i-1]] + k * V[i-1] };; k表示拿了k个第i种物品;
  5. 实际上3中的k如果限定k = 0,1, 那么就变成了2;
  6. backpack 3: 实际上可以优化成f[i][w] = max(f[i-1][w], f[i][w - A[i-1]] + V[i-1]!!!!!!!
    1
    2
    3
    4
    5
    6
    解释: 
    e.g. Suppose w=5, A[i-1] = 2, V[i-1] = x

    f[i][5] = max(f[i-1][5], f[i-1][3]+x, f[i-1][1]+2x;
    f[i][7] = max(f[i-1][7], f[i-1][5]+x, f[i-1][3]+2x, f[i-1][1]+3x)
            = max(f[i-1][7], f[i][5]+x);

这样就把4中的转移方程的O(n*m^2)降低时间复杂度为O(n*m);

实际上写起来很简单，跟backpack 2类似, 只有一个地方的i-1变成了i, 但是这个状态转移方程的推导有点吊

我tmd能做到这么巧妙绝伦的题，真是非常荣幸

可是，实际上从一维的角度仔细想一下, 如果从backpack6的思路，因为是无序的，直接考虑最后一个物品是谁, 那么状态转移方程直接就是f[j] = Math.max(f[j], f[j - A[i-1]] + V[i - 1]), 根本就没有那个优化状态方程的过程了

所以, 只要是“可以用无穷多次”, 直接从最后一个物品是谁下手就好了

背包最后的小结:

  1. Backpack: 可行性背包
  • 题面: 要求不超过target时能拼出的最大重量
  • 记录f[i][w]=前i个物品能不能拼出重量w
  1. Backpack V, Backpack VI: 计数型背包
  • 题面: 要求有多少种方式拼出重量w
  • 记录f[i][w]=前i个物品有多少种方式拼出重量w
  1. Backpack II, Backpack III: 最值型背包
  • 题面: 要求能拼出的最大价值
  • 记录f[i][w]=前i个/种物品拼出重量w能得到的最大价值

关键：

  1. 最后一步
  • 最后一个背包内的物品是哪个(没有顺序的情况下)
  • 最后一个物品有没有放进背包(有顺序)
  1. 数组大小和最大承重target相关
  2. 空间优化: 由(m n)二维数组，优化为(m 2)二维数组，再优化为长度为m的一维数组

区间型dp

  • 给定一个序列／字符串，进行一些操作
  • 最后一步是将序列/字符串去头/去尾
  • 剩下的是一个区间[i,j]
  • 状态自然定义为f[i][j], 表示面对自序列[i, ...j]时的最优性质

解法: 几乎都是定义f[i][j]为[i,j]区间对应的要求的东西, 然后分三种情况:

  1. 去头;
  2. 去尾;
  3. 去头去尾;

e.g. Longest Palindrome Subsequence;

注意: 这个题dp的顺序只能按照长度从小到大算, 并不能从i开始算; 因为转移方程是f[i][j] = max{ f[i+1][j], f[i][j-1], f[i+1][j-1]+2|S[i]==S[j] }; 如果按照i从小到大的顺序，f[i+1][j]还没有算出来: 有问题; 而f[i][j]的长度比max里面的分别多1,1,2, 所以应该按照长度算;

方法:

  1. dp: 递推; f[0], f[1], … f[n]: 从下往上;
  2. memo + dfs: 递归; f(n), f(n-1), … f(1): 从上往下;
  3. 区间型dp因为是按长度dp，所以比较适合memo+dfs: 这样memo中还是按照正常的i,j遍历,递归的计算都是在dfs中算的;

e.g.

  • Longest Palindrome Subsequence:
    1. dp; erode both ends: 3 scenarios;
    2. memo + recursion;
  • Coins in a line III:
    1. 区间型 + game theory;
    2. payoff relation => f[i][j]的状态转移方程
  • Scramble String:
    1. 看最后一步: S1-T1, S2-T2 或者 S1-T2, S2-T1; 最后一步2个string的两段有没有交换;
    2. 每一个对应的部分, enumerate所有的可能;
    3. 4维dp降低为3维dp: 找隐含信息降维;
  • Burst Balloons:
    1. 消去型: 一定不能顺着“消去”的思想做，因为每次消去之后左右两边的变为adjacent, 要手动变为adjacent,要记录消去的index…❌
    2. 看最后一步: index k对应的那个是最后消去的, 那么左右两边的从一开始到最后都是独立的;
    3. 从2看出实际上是区间缩小的子问题: dp，想出对应的状态转移方程

双序列型dp:

f[m][n]二维对应两个string/array;

  1. Longest Common Subsequence (LCS);
  2. Interleaving String;
  3. Edit Distance: A和B同时变是没有区别的，等价于只变一个
  4. Distinct Subsequences: f[i][0]初始化的时候小心: 用后面举例来看这个应该是多少
1
2
3
4
5
6
7
8
9
10
空间优化之滚动数组: 
1. f[m][n] --> f[2][n];
2. int old, now;
3. 两层循环i, j: 每次进外层循环的时候old, now互换;
4. 循环体中的f[i][j] -> f[now][j], f[i-1][j] -> f[old][j];
5. 上面: 存在型，计数型，最值型都出现了(其实dp就是解决这种问题的, 背包问题中也是这些问题); 
6. 从上面看出双序列的规律非常强，都是`f[m][n]`,最开始初始化, 初始化的时候难以判断的时候注意初始化为0/1; 都是`i,j`的常规循环.
7. Regular Expression Matching
8. Wildcard Matching: `*`匹配0-多个，但是还有别的东西，所以并不一定regex一定能匹配
这道题最后打印int[] res, res是长度为m的数组, 表明每个A中的字符匹配B中的哪个字符: A[i]匹配B[res[i]]