DynamicProgramming

动态规划套路

有一个 m*n 大小的矩阵迷宫，每次移动只能向右或者向下，文聪左上角到右下角有多少种不同的走法

暴力解法

• 从(1,1)->(m,n)的不同路径中有大量的重复，比如(1,1)->(i,j)有 k 条不同的路径，那么对于任何一条固定的路线(i,j)->(m,n)的路径，都需要走 k 遍来模拟。
• 不关心具体的走法，只关心状态，也就是走法的数量
• 同理，如果知道(i,j)->(m,n)有 k 条不同的路径，那么(1,1)->(i,j)->(m,n)的不同路径总数是k*s

动态规划

• 令(i,j)表示从(1,1)->(i,j)的不同路径数量，f(i,j) = f(i-1,j) + f(i,j-1)
• 如果要求出 f(i,j) 只需要上一个结果即可， 也就是求解f(i,j) 需要求出子问题f(i',j')

动态规划适用前提

无后效性

• 一旦确定f(i,j)，就不用关心如何计算出f(i,j)
• 想要确定f(i,j)，只要知道f(i-1,j)和f(i,j-1)

最优子结构

• f(i,j)的定义已经蕴含最优
• 大问题的最优解可以由若干小问题的最优解推出(min, max, sum)

  DP 适用的问题：可以将大问题拆成几个小问题，且无后效性，具有最优子结构的性质

记忆化递归

• 可以使用递归求解
• 有重复子问题，overlaping subproblem

套路一：基本类型（时间序列）

House Robber

• 给一排房子，相邻的房子不能抢，问最多能抢的价值
• 房子只有抢和不抢两个状态
• 和时间相关的为第 i 轮

class Solution {
public:
    int rob(vector<int>& nums) {
        // 0 --> max profit of not rob the i-th house
        // 1 --> max profit of robbing the i-th house
        // corner case
        if (nums.empty()) return 0;
        vector<vector<int>> dp(nums.size() + 1, vector<int>(2,0));
        // if not rob 0 max profit is 0
        dp[0][0] = 0;
        // if rob 0, max profit is nums[0]
        dp[0][1] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            // if not rob the i-th roby, so the max profit will be the max value of rob/non-rob on last house
            // because if rob on a low price house will not be a good choice
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            // if decide to rob i-th , i-1-th must not be robbed
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

House Robber II

• 给一圈“首尾相连”的房子，相邻的房子不能抢，问最多能抢的价值
• 假定有 n 个房子，因为 0 和 n-1 为相邻的房子。因此可抢的范围为 0 -> n-2 或者 1 -> n-1
• 因此结果就是两个中最大值。

  class Solution {
  public:
      int rob(vector<int>& houses) {
          const int m = nums.size();
          if (m < 2) return m ? nums[0] : 0;
          function<int(int,int)> robHelper = [&](int l, int r){
              vector<vector<int>> dp(m+1, vector<int>(2, 0));
              dp[l][1] = nums[l];
              for (int i = l; i <= r; i++) {
                  if (i == 0) continue;
                  dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
                  dp[i][1] = dp[i-1][0] + nums[i];
              }
              return max(dp[r][0], dp[r][1]);
          };
  
          return max(robHelper(1, m-1), robHelper(0, m-2));
      }
  };

Best Time to Buy and Sell Stock III

• 给定一系列每日股票的价格，每日只能买入、卖出、不操作。最多交易两次，问最大的收益
  

/*
    0 表示这一轮我已经持有第一股的最大收益
    1 表示这一轮我已经售出第一股的最大收益
    2 表示这一轮我已经持有第二股的最大收益
    3 表示这一轮我已经售出第二股的最大收益
*/
  for (int i = 1; i <= n; i++) {
      dp[i][0] = max(dp[i-1][0], -val[i]);
      dp[i][1] = max(dp[i-1][1], dp[i-1][0] + val[i]);
      dp[i][2] = max(dp[i-1][2], dp[i-1][1] - val[i]);
      dp[i][3] = max(dp[i-1][3], dp[i-1][2] + val[i]);
  }
  ans = max{dp[n][i]} (i = 0,1,2,3)

Best Time to buy and Sell Stock with cooldown

• 给定一系列股票的加个，每日只能买入、卖出、不操作。买入后要隔卖出，无总交易限制，问最大收益
  

  /*
      0 表示本轮刚持有股票的最大收益
      1 表示本轮持有一天以上的最大收益
      2 表示我已清空股票的最大收益
  */
  for(int i = 1; i <= n; i++) {
      dp[i][0] = dp[i-1][2] - val[i];
      dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
      dp[i][2] = max(dp[i-1][2], dp[i-1][1] + val[i]);
  }
  ans = max{dp[i][n]} (n = 1, 2, 3)

Wiggle Subsequence

• 给定一个序列 s， 求其最长的wiggle pattern subsequence (.... >s[i] < s[j] > s[j+1]...)
  

/*
    0 以当前元素结尾且上升
    1 一当前元素结尾且下降
*/
for (int i = 1; i <= N; i++) {
    if (nums[i] > nums[i-1]) {
        dp[i][0] = dp[i-1][1] + 1;
    }
    if (nums[i] < nums[i-1]) {
        dp[i][1] = dp[i-1][0] + 1;
    }
    ans = max(dp[N][i]) (i = 0, 1)
}

Paint Fence

• 给出 cost[i] 表示第 i 个房子喷涂第 j 中 漆的价格，相邻的房子不能涂同一种颜色，求喷涂所有房子的最小价格

/*
    dp[i][j] 表示第 i 间房子喷涂第 j 中颜色的代价
*/
for (int i = 1; i <= N; i++) {
    dp[i][j] = min(dp[i-1][j], cost[j]) // j = 1,2,...,k
}
ans = min(dp[N][j]) (j = 0,1,2,...,k)

To Do or Not To Do
很多不那么套路的 DP 题目，状态比较难以设计，某些题目会给你“行使某种策略的权利”，想买卖股票的题目，两个状态就分别为“行驶了某种权利”，“没有行使某种权利” 分别对应的价值

Max Consecutive One II

• 给定一个数组(0/1)，有最多一次从 0 翻转到 1 的权利，问最多可以有多少连续的 1
  

/*
    0 表示以当前元素结尾且没有行使翻转权利的最长连续 1
    1 表示以当前元素结尾且已经行驶翻转权利的最长连续 1
*/
for (int i = 1; i <= N; i++) {
    dp[i][0] = max(dp[i-1][0] + nums[i], nums[i]);
    dp[i][1] = max(dp[i-1][0],dp[i-1][1]+nums[i]);
}
ans = max(dp[i][j]) (for all possible i,j = 0,1)

套路二：基本类型 II（时间序列加强版）

• 给定一个序列（数组/字符串），其中每个元素可以认为一天，但今天的状态和之前的某一天有关，需要挑选。
• 套路

定义 dp[i] 表示第 i 轮的状态，一般这个状态要求和元素 i 直接有关系。
千方百计将 dp[i] 与之前的状态 dp[i’] 产生关系比如 sum,max,min,
dp[i] 一定不能与大于 i 的轮次有关系，否则违反了 DP 的无后效性。

• 最终的结果是 dp[i] 中的某一个
  

Longest Increasing Subsequence

• 给定一个数组 s，求最长的递增子序列的长度

状态定义： 照抄问题，dp[i]–> s[1:i]里面以 s[i]为结尾的、最长的递增子序列的长度。
状态转移：寻找最优解的前驱状态 j，将 dp[i] 与 dp[j] 产生联系

for (int i = 1; i <= N; i++) {
    //i 表示 LIS 的最大元素，搜索该 LIS 的第二大元素
    for (int j = 1; j < i; j++) {
        if (nums[i] < nums[j])
            dp[i] = max(dp[i], dp[j]+1);
    }
}
ans = max(dp[i]), for i in 1,...N

Largest Divisible Subset

• 给定一个数组 s，求最大子集，使得里面的所有元素之间都可以相互整除。

状态定义：照抄问题，dp[i]–> s[1:i] 以 s[i]为结尾，满足题目要求的最大子集的数目。
状态转移：寻找最优的前驱状态 j，将 dp[i] 与 dp[j] 产生联系

sort(nums);
for (int i = 1; i <= N; i++) {
    // i 表示该集合的最大元素，搜索该子集的第二大元素 j
    for (int j = 1; j < i; j++) {
        if (nums[i] % nums[j] == 0)
            dp[i] = max(dp[i], dp[j]+1);
    }
}
ans = max(dp[i]) for i in 1,...,N

Filling Bookcase Shelves

• 给定 N 本书（宽高各异）的序列要求按照所给的顺序摆放，相邻的若干本书可以放一层，但同一层的高度不能超过 w。问这个书架最矮可以有多高
  
• 将数组 S 分成若干个子数组，最小化“每个数组的最大值之和”，输出该值

状态定义：照抄问题 dp[i]–>将数组S[1,…N] 分成若干个子数组，最小化“每个子数组的最大值之和”，保存该值
状态转移：寻找最优的前驱状态 j，将 dp[i] 与 dp[j] 产生联系
第 i 本书所在的这一层可能有多高？取决于上一层的最后一本书放在那里

for (int i = 1; i <= N; i++) {
    // i 表示本层最后一本书，搜索上一层最后一本的位置
    for (int j = i-1; j >= 1; j--) {
        if (totalWidth[j+1:i] <= W)
            dp[i] = min(dp[i], dp[j] + maxHeight[j+1:i]);
        else
            break;
    }
}
ans = dp[N];

套路三：双序列类型

• 给出两个序列 s 和 t（数组/字符串），对他们搞事情
• 套路

定义 dp[i][j]: 表示针对 s[1:i] 和 t[1:j] 的子问题求解答
千方百计将 dp[i][j] 与之前的状态之间转移 dp[i-1][j], dp[i][j-1] , dp[i-1][j-1]
最终的结果是 dp[m][n]

Longest Common subsequences

• 求字符串 s 和 t 的 length of LCS

状态定义：照抄问题 dp[i][j]–> s[1:i] t[1:j]的 length of LCS
状态转移：外面两大层循环编译 i 和 j，核心从 s[i] 与 t[j] 的关系作为突破口，往 dp[i-1][j], dp[i][j-1], dpp[i-1][j] 转移

/*
    s:XXXXXi
    t:YYYj
*/
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s[i] == t[j]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

Shortest Common Supersequence

• 求字符串 s 和 t 的 length of SCS

状态定义：照抄问题 dp[i][j]–> s[1:i] 和 t[1:j] 的 length of SCS
状态转移：外面两层大循环遍历 i 和 j ：核心从 s[i] 与 t[j] 的关系作为突破口，拼命往 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s[i] == t[j]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
        }
    }
}

Edit Distance

• 求字符串 s 和 t 的 min edit distance

状态定义：照抄问题 dp[i][j]–> s[1:i] 和 t[1:j] 的 min edit distance
状态转移：外面两层大循环遍历 i 和 j ：核心从 s[i] 与 t[j] 的关系作为突破口，拼命往 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移

套路四：第一类区间类型

套路五：第二类取件类型

套路六：背包入门

状态压缩