动规动规

发表于 更新于

DP主要用来解决两类问题：计数，优化。计数是说给一些资源，去得到某种解的方法数有多少或者得到某种解的最（大/小）值。优化是说很多时间复杂度达到2^n的搜索、递归问题可以用DP来优化。

使用DP有三个要求：最优子结构（把大问题分为多个小问题，只要最优解决小问题就可以最优解决大问题），子问题被重复求解（overlapped，重复了才能优化嘛），没有后效性（子问题的最优解不会在解决后面的较大问题时被改变）。

获得状态转移方程是最难的一步，总结了一点点思路

1. 遍历以求得的所有解

得到某一种状态需要遍历前面所有已经得出的状态，即求 f[i] 需要遍历 f[1], f[2], …, f[i - 1]。139，813，312，300，410都是这样。

还有312题戳破气球f[i][j]需要遍历 f[i][k] 和 f[k][j] 两个状态。

139、单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean wordBreak(String s, List<String> wordDict) {
    // f[i] 从第1个到第i个字符的子字符串能否被拆分
    // f[i] = (f[1]...f[k] && dict.contains(s.substring(k, i)))   k >= 0 && k < i
    // 时间复杂度：O(n^2)  空间复杂度：O(n)

    HashSet<String> dict = new HashSet<>();
    for (String str : wordDict) {
      dict.add(str);
    }
    boolean[] f = new boolean[s.length() + 1];
    f[0] = true;
    for (int i = 1; i <= s.length(); i++) {
      for (int k = 0; k < i; k++) {				//这里遍历所有可能解
        if (f[k] && dict.contains(s.substring(k, i))) {
          f[i] = true;
          break;
        }
      }
    }
    return f[s.length()];
}

873题一维数组无法表示状态，也需要二维来记录所有以i，j结尾的子序列的长度，并利用HashMap来进行记忆

2. 状态机

在某一个时刻或位置会有几种不同的状态，不同状态间的转换有一些限制，用这些限制就可以写出状态转移方程。比如309、801题

309、存在冷却期的股票买卖

在卖出后必须冷却一天才能继续买入，每天只能干三件事，买入、啥也不干、卖出。那么状态可以直接设为这3种情况吗？

实际上不行，因为这里啥也不干包括了2种情况：手里持股啥也不干和不持股啥也不干。那分为四个状态呢？就可以进行计算了。这里还可以降维：

1
2
3
4
f[i][0]  买入。     = f[i - 1][2] - A[i]
f[i][1]  持股啥也不干   = max(f[i - 1][0], f[i - 1][1])
f[i][2]  不持股啥也不干 = max(f[i - 1][2], f[i - 1][3])
f[i][3]  卖出。     = max(f[i - 1][0], f[i - 1][1]) + A[i]

不过前两种状态实际上也可以合并为一个状态，那就是存在3种状态，持有、休息、卖出：

image.png 
1
2
3
f[i][0]  到第i天持有     = max(f[i - 1][0], f[i - 1][1] - prices[i])
f[i][1]  到第i天休息状态  = max(f[i - 1][1], f[i - 1][2])
f[i][2]  到第i天售出状态  = f[i - 1][0] + prices[i]

（72题编辑距离中每一步有四种操作方式达到，这状态转移也是有点类似的哦）

3. 问题转化

比如576题，将(i, j) 位置上的球移出界的路径数可以转化为将界外的球移到 (i, j) 位置的路径数；

416分割等和子集的题可以转为求和为是否存在和为 sum 一半的子序列

4. 关于矩阵的

  1. 通过dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i -1][j -1];先计算出所有左上角到 (i, j) 点的矩形区域的和
  2. 然后可以快速得到任意指定矩形区域的和，区域 (x1, y1) 到 (x2, y2) 的和为 dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];

比如1292，1314题，在 n^2 时间内就可以得到所有区域的和了，否则时间复杂度将达到 n^4

5. 空间压缩

很多题都可以进一步压缩空间复杂度，这种题大多数状态转移方程只需要用到前一层或后一层状态，所以可能需要一个额外的一维数组或者变量进行记录，比如121，416题等。322零钱兑换也是不错的。

121: f[i] = max(f[i - 1], A[i] - l[i]) l[i] 表示前i天的最低价。 >>>> res = max(res, A[i] - lowest) 用lowest代替 L 数组

416: f[i][j] = f[i - 1][j] || f[i - 1][j - A[i]] >>>> f[j] = f[j] || f[j - A[i]]

f[i][j] = f[i - 1][j] >>>> memo = f; memo[j] = f[j]; f = memo 声明一个memo数组，最后再全部赋值给f

f[i][j] = f[i + 1][j - 1] 这个i由i+1得到，所以要倒序遍历i >>>> f[i] = max(f[i], f[i - 1]) ，但要记录前一个值，详细看下面516题

516、最长回文字子串题就可以用到滚动数组进行压缩，滚动数组还可以进一步压缩为一个临时变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int longestPalindromeSubseq(String s) {
  // f[i][j]   从第i个字符到第j个字符是否是回文字
  // f[i][j] = f[i + 1][j - 1]  if (s[i] == s[j])

  // 滚动数组
  int[] f0 = new int[s.length() + 1];   //状态压缩，f0[i]表示长度为l - 1的到第i个字符为止的字符串

  if (s.equals("")) return 0;

  for (int i = 1; i <= s.length(); i++) f0[i] = 1;
  
  for (int i = s.length(); i >= 1; i--) {
    int pre = 0;
    for (int j = i + 1; j <= s.length(); j++) {
      int temp = f0[j];
      if (s.charAt(i - 1) == s.charAt(j - 1)) {
        f0[j] = pre + 2;
      } else f0[j] = Math.max(f0[j], f0[j - 1]);
      pre = temp;
    }
  }
  return f0[s.length()];
}

486题赢家预测，状态转移方程是f[i][j] = Math.max(nums[i - 1] - f[i + 1][j], nums[j - 1] - f[i][j - 1]); f[i][j]表示第i到j元素的先手比后手赢的最多分数，这种写法没法降维了。不过把f[i][j]改为长度为 i，开始元素是j的子序列中先手比后手多的分数的话就可以降维了，max(nums[j] - f[i - 1][j + 1], nums[j + i - 1] - f[i - 1][j]); >>>> f[j] = max(nums[j] - f[j + 1], nums[j + i - 1] - f[j])

6. Other

还有些题连状态方程都很难想，比如486猜赢家，f[i][j]表示从i到j的子序列，先手和后手的分差。啊凭经验与运气了。

有时还需要一个HashMap记录之前的状态来快速获取结果，如823，873。

那就先写这么多，之后有新的想法再更新，那我现在走吧。我是郭富城！