[数据结构与算法]动态规划算法总结

一、模板

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
  for 状态2 in 状态2的所有取值:
    for ...
      dp[状态1][状态2][...] = 求最值(选择1， 选择2，...)

二、解题套路

1. 明确【状态】
2. 明确【选择】
3. 明确dp函数/数组的定义
4. 明确base case

三、状态压缩

如果计算状态dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩技巧，将二维dp转化为以为，将空间复杂度从O(N^2)降低到O(N).

四、子序列解题模板：最长回文子序列

1、第一种思路是一个一维的dp数组：

int n = array.length;
int []dp = new int[n];
for(int i = 1;i<n;i++){
  for(int j = 0;j<i;j++){
    dp[i] = 最值(dp[i], dp[j] + ...)
  }
}

2、第二种思路模板是一个二维dp数组

int n = arr.length;
int [][] dp = new dp[n][n];
for(int i = 0;i<n;i++){
  for(int j =1;j<n;j++){
    if(arr[i]==arr[j]){
      dp[i][j] = dp[i][j] + ...
    }else{
      dp[i][j] = 最值(...)
    }
  }
}

3、涉及两个字符串/数组时(比如最长公共子序列)，dp数组的含义如下：

(1) 在子数组arr[0,…i]和子数组arr2[0,…,j]中，我们要求的子序列(最长公共子序列)长度为dp[i][j]
(2) 只涉及一个字符串/数组时，dp数组的含义如下：
在子数组array[i…j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]

4、动态规划的状态转移关系

1、明确dp数组的定义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
2、根据dp数组的定义，运用数学归纳法的思想，假设dp[0,…,i-1]都已知，想办法求出dp[i],一旦完成这一步，真个题目基本就解决了

5、背包问题

(1) 明确【状态】：【背包容量】【可选择的物品】
(2) 明确【选择】：【装进背包】【不装进背包】
(3) 明确dp数组的定义：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]
比如说dp[3][5] = 6， 其含义为：对于给定的一系列物品中，若只对前3个物品进行选择，当背包容量为5时，最多可装下的价值为6

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // base case 已初始化
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],
                               dp[i - 1][w]);
            }
        }
    }

    return dp[N][W];
}

6、股票问题

动态规划算法本质上就是穷举【状态】，然后再【选择】上选择最优解

（1）穷举状态：天数i，允许交易的最大次数k，当前的持有状态0 or 1。
（2）穷举选择： 买入，卖出，无操作

dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
// n为天数，大K为交易数的上限，0 和 1代表是否持有股票
// 此问题共n*K*2种状态，全部穷举就可搞定

for 0 <= i < n:
  for 1 <= k <=K:
    for s in {0,1}:
      dp[i][k][s] = max(buy, sell, rest)

(3) 状态转移方程
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max(今天选择rest, 今天选择sell)
解释： 今天我没有持有股票，有两种可能，我从这两种可能中求最大利润

1. 我昨天就没有持有，且截至昨天最大交易次数限制为k,然后我今天选择rest，所以我今天还是没有持有，最大交易次数限制依然为k
   2、 我昨天持有股票，且截至昨天最大交易次数限制为k; 但是今天我sell了，所以我今天没有持有股票了，最大交易次数限制依然为k

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 今天选择 rest, 今天选择 buy )

1、我昨天就持有股票，最大交易次数限制为k，那么对于昨天来说，有两种可能，我从这两种可能中求最大利润
2、我昨天本没有持有，且截至昨天最大交易次数限制为k-1,但今天我选择buy,所以今天我就持有股票了，最大交易次数限制依然为k
3. 注意 k 的限制，在选择 buy 的时候相当于开启了一次交易，那么对于昨天来说，交易次数的上限 k 应该减小 1。

(4) base case

dp[-1][…][0] = 0
解释： 因为i是从0开始的，所以i=-1意味着还没有开始，这时候的利润当然是0

dp[-1][…][1] = -infinity
解释： 还没开始的时候，是不可能持有股票的
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值

dp[…][0][0] = 0
解释： 因为k是从1开始的，所以k=0意味着根本不允许交易，这时候的利润当然是0

dp[…][0][1] = -infinity
解释： 不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值

（5）总结

base case：
dp[-1][...][0] = dp[...][0][0] = 0
dp[-1][...][1] = dp[...][0][1] = -infinity

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

7、打家劫舍问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

(1)明确状态：面前房子的索引就是状态
(2)明确选择: 抢和不抢
(3)状态转移：
如果你抢这间房子，那么你肯定不能抢相邻的下一间房子了，只能从下下间房子开始做选择
如果你不抢这间房子，那么你可以走到下一间房子前，继续做选择

  int res = Math.max(
           // 不抢，去下家
           dp(nums, start + 1),
           // 抢，去下下家
           nums[start] + dp(nums, start + 2)
       );

  int res = Math.max(
           // 不抢，去下家
           dp(nums, start + 1),
           // 抢，去下下家
           nums[start] + dp(nums, start + 2)
       );