LeetCode 八周 - 动态规划专题 - 《算法学习笔记》

https://leetcode-cn.com/problems/maximum-subarray/">最大子序和 https://leetcode-cn.com/problems/maximum-subarray/
https://leetcode-cn.com/problems/triangle/">三角形最小路径和 https://leetcode-cn.com/problems/triangle/
https://leetcode-cn.com/problems/unique-paths-ii/submissions/">不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/submissions/
https://leetcode-cn.com/problems/longest-increasing-subsequence/">最长上升子序列 https://leetcode-cn.com/problems/longest-increasing-subsequence/
https://leetcode-cn.com/problems/edit-distance/submissions/">编辑距离 https://leetcode-cn.com/problems/edit-distance/submissions/
https://leetcode-cn.com/problems/coin-change-2/submissions/">零钱兑换 II https://leetcode-cn.com/problems/coin-change-2/submissions/
https://leetcode-cn.com/problems/strange-printer/">奇怪的打印机 https://leetcode-cn.com/problems/strange-printer/
https://leetcode-cn.com/problems/regular-expression-matching/">正则表达式匹配 https://leetcode-cn.com/problems/regular-expression-matching/

动态规划

DP考虑方式

状态表示
1. 集合是什么
2. 属性（最大，最小，数量）
状态计算——集合的划分

最大子序和 https://leetcode-cn.com/problems/maximum-subarray/
状态表示 f[i]
1. 集合是什么？| 所有以 i 结尾的子段
2. 属性| 最大值

状态计算| f[i] = max(f[i - 1], 0] + nums[i]

class Solution {
public:
 int maxSubArray(vector& nums) {
     int last = 0, res = INT_MIN;
     for (auto num : nums) {
         last = max(last, 0) + num;
         res = max(res, last);
     }
     return res;
 }
};

三角形最小路径和 https://leetcode-cn.com/problems/triangle/

状态表示
1. 集合是什么？f[i][j] 表示以 triangle[i][j] 为终点的所有路线
2. 属性？所有路线的最小值
状态计算？
1. 最后一步从左上下来的
2. 最后一步从右上下来的
3. f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j]
// 从底向上滚动数组 ```cpp

class Solution { public: int minimumTotal(vector& tri) {

 int n = tri.back().size();
 vector f(tri.back().begin(), tri.back().end());
 for (int i = n - 2; i >= 0; i--)
 for (int j = 0; j < tri[i].size(); j++)
 f[j] = min(f[j], f[j + 1]) + tri[i][j];
 return f[0];

} }; ```

不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/submissions/

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<long long>> vec(n, vector<long long>(m, 0));
        vec[0][0] = grid[0][0] ? 0 : 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) continue;
                if (i) vec[i][j] += vec[i - 1][j];
                if (j) vec[i][j] += vec[i][j - 1];
            }
        return vec[n - 1][m - 1];
    }
};

状态表示 dp[i][j]
1. 集合是什么？以 (i, j) 为终点的所有路径
2. 属性？所有路径的数量
状态运算（集合划分）对于(i, j) 而言，集合可以分为两类 1. 从上边过来的 2. 从左边过来的那么路径的数量可以表示成 dp[i - 1][j] + dp[i][j - 1]

解码方法 https://leetcode-cn.com/problems/decode-ways/submissions/

class Solution {
public:
  int numDecodings(string s) {
      int n = s.size();
      vector<int> f(n + 1);
      f[0] = 1;
      for (int i = 1; i <= n; i++) {
          if (s[i - 1] != '0') f[i] = f[i - 1];
          if (i >= 2) {
              int val = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
              if (val >= 10 && val <= 26) f[i] += f[i - 2];
          }
      }
      return f.back();
  }
};

状态表示 f[i]
1. 集合是什么？以 i 结尾的所有解码出来的字符串
2. 属性？字符串数量
状态计算（集合划分）以 i 结尾的字符串，只会有两种情况
1. 以 i - 1 为结尾的字符串集合加上 i 字符
2. 以 i - 2 为结尾的字符串集合，加上 (i - 1, i)
f[i] = f[i - 1] + f[i - 2]

打家劫舍 https://leetcode-cn.com/problems/house-robber/

class Solution {
public:
  int rob(vector<int>& nums) {
      if (nums.empty()) return 0;
      int n = nums.size();
      vector<int> f(n + 1);
      f[1] = nums[0];
      for (int i = 2; i <= n; i++) {
          f[i] = f[i - 2] + nums[i - 1];
          if (i >= 3) f[i] = max(f[i], f[i - 3] + nums[i - 1]);
      }
      return max(f[n], f[n - 1]);
  }
};

状态标识 f[i]
1. 集合？选第 i 个元素构成的所有集合
2. 属性？最大值
状态计算f[i] 只可能由两种情况转过来
1. 选f[i - 2]
2. 选f[i - 3]
再往后，比如 f[i - 4, f[i - 5]，因为选 f[i - 4] 的话，一定可以选 f[i - 2]使结果更优，f[i - 5]同理

f[i] = max(f[i - 2], f[i - 3]) + nums[i]
第二种做法

class Solution {
public:
  int rob(vector<int>& nums) {
      int n = nums.size();
      vector<int> f(n + 1), g(n + 1);
      for (int i = 1; i <= n; i++) {
          g[i] = max(f[i - 1], g[i - 1]);
          f[i] = g[i - 1] + nums[i - 1];
      }
      return max(f[n], g[n]);
  }
};

状态表示 f[i], g[i]
选第 i 个物品构成的合法序列 f[i]
不选第 i 个物品构成的合法序列
最大值
状态计算
f[i] = g[i - 1] + nums[i]
g[i] = max(f[i - 1], g[i - 1])

最长上升子序列 https://leetcode-cn.com/problems/longest-increasing-subsequence/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int max_len = 0;
            for (int j = 1; j < i; j++)
                if (nums[j - 1] < nums[i - 1]) max_len = max(max_len, dp[j]);
            dp[i] = max_len + 1;
        }
        return *max_element(dp.begin(), dp.end());
    }
};

状态表示 dp[i]
1. 集合是什么？以 i 结尾的最长上升子序列的集合
2. 属性？集合的最大长度
状态计算
dp[i] = max(dp[j]) + 1 (0 ≤ j < i && nums[j] < nums[i])

编辑距离 https://leetcode-cn.com/problems/edit-distance/submissions/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int i = 0; i <= m; i++) dp[0][i] = i;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m && j <= m; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                else
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        return dp[n][m];
    }
};

状态表示 dp[i][j]
1. 集合？word1 的前 i 个字母转换成 word2 的前 j 个字母的所有操作集合
2. 属性？某个最小的集合
属性计算dp[i][j] 可能通过3种方式转变过来
1. 插入，dp[i][j - 1] + 1
2. 删除，dp[i - 1][j] + 1
3. 替换，dp[i - 1][j - 1] + word1[i] == word2[j] “ 0 : 1

代码里需要注意初始化的问题
dp[0][i] 说明把 word1 的前0个字母，转成 word2 的前 i 个字母，需要进行 i 此操作（插入）
dp[i][0] 说明，把word1 的前 i 个字母，转成 word2 的前 0 个字母，需要进行 i 此操作（删除）

零钱兑换 II https://leetcode-cn.com/problems/coin-change-2/submissions/

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1);
        int n = coins.size();
        f[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= amount; j++)
                if (j >= coins[i]) f[j] += f[j - coins[i]];
        return f[amount];
    }
};

可以看成完全背包

状态表示 f[i, j]
1. 集合是什么？前 i 种物品，凑出钱为 j 的方案
2. 数量
状态计算
f[i, j] = f[i - 1, j] + f[i - 1, j - c] + f[i - 1, j - 2c] + … + f[i - 1, j - kc]
f[i, j - c] = f[i - 1, j - c] + f[i - 1, j - 2c] + … + f[i - 1, j - kc]
所以
f[i, j] = f[i - 1, j] + f[i, j - c]

然后可以利用滚动数组优化，但因为这里的依赖只有前一个状态和 f[i, j -c]，而 f[i, j - c] 一定已经被算出来了，所以可以优化成一维的

奇怪的打印机 https://leetcode-cn.com/problems/strange-printer/

状态表示 f[L,R]
1. 集合？所有将[L,R]染成最终样子的方式
2. 属性？最小数量
状态计算（保证长度短的先求）F[L, R] 可以由这么几类转移过来
1. 1 + F[L + 1, R]：左边只染第一个，右边自然是 F[L + 1, R]（长度小于F[L, R]）
2. F[K - 1, R] + F[K + 1, R]：当s[k] == s[l] 的时候左边染 k 个，右边自然是 F[K + 1, R]为什么只能是 ==，不能是 ≠，如果 ≠
  1. F[L, R] = F[L, K] + F[K + 1, R]
  2. 属于废话，如果存在 k == l（字符），那么这个 F[L, R] 不会被他更新，如果不存在 k == l，这个答案等价于 1 + F[L + 1, R]，加上也不会错
```
class Solution {
public:
int strangePrinter(string s) {
if (s.empty()) return 0;
int n = s.size();
vector<vector> f(n + 1, vector(n + 1));
for (int len = 1; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
   int r = l + len - 1;
   f[l][r] = f[l + 1][r] + 1;
   for (int k = l + 1; k <= r; k++)
       if (s[l] == s[k]) f[l][r] = min(f[l][r], f[l][k - 1] + f[k + 1][r]);
       else f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
}
return f[0][n - 1];
}
};
```

正则表达式匹配 https://leetcode-cn.com/problems/regular-expression-matching/

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        s = ' ' + s, p = ' ' + p;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                if (!i && !j) {
                    f[i][j] = true;
                } else {
                    if (j + 1 <= m && p[j + 1] == '*') continue;
                    if (p[j] != '*') {
                        if (i && j && (s[i] == p[j] || p[j] == '.') )
                            f[i][j] = f[i - 1][j - 1];
                    } else {
                        if (j >= 2) f[i][j] = f[i][j - 2];
                        if (i > 0 && j > 0) f[i][j] = f[i][j] || f[i - 1][j] && (p[j - 1] == '.' || s[i] == p[j - 1]);
                    }
                }
        return f[n][m];
    }
};

状态表示 f[i][j]
1. 集合？s 匹配前 i 个，p 匹配前 j 个的情况
2. 属性？true 或者 false
状态计算（集合划分）f[i][j] 可以由以下几种情况转移过来
1. p[j] != ‘*’
  f[i][j] = f[i-1][j-1] 当 s[i] 和 p[j] 匹配时
2. p[j] == ‘*’
  - 匹配 0 个，f[i][j] = f[i][j - 2]
  - 匹配 1 个，f[i][j] ||= f[i - 1][j - 2] && s[i] 和 p[j-1] 匹配
  - 匹配 2 个，f[i][j] ||= f[i - 2][j - 2] && s[i - 1 … i] 和 p[j - 1] 匹配
  - 匹配 n 个，f[i][j] ||= f[i - n][j - 2] && s[i - n + 1 … i] 和 p[j - 1] 匹配
3. f[i - 1][j]（类似完全背包的优化）
  - 匹配 0 个，f[i - 1][j] = f[i - 1][j - 2]
  - 匹配 1 个，f[i - 1][j] ||= f[i - 2][j - 2] && s[i - 1] 和 p[j - 1] 匹配
  - 匹配 2 个，f[i - 1][j] ||= f[i - 3][j - 2] && s[i - 2 … i - 1] 和 p[j - 1] 匹配
  - 匹配 n 个，f[i - 1][j] ||= f[i - 1 - n][j - 2] && s[i - n … i - 1] 和 p[j - 1] 匹配
4. 所以可以优化一下，即 f[i][j] = f[i][j - 2] || (f[i - 1][j] && s[i] 和 p[j - 1] 匹配)

需要注意几个点

如果 p[j + 1] == ‘*’，说明 j 和 j + 1 是绑定的，不能单算

动态规划专题