DynamicPro.md

动态规划总结

遍历方向

// 斜着遍历数组
for (int l = 2; l <= n; l++) {
    for (int i = 0; i <= n - l; i++) {
        int j = l + i - 1;
        // 计算 dp[i][j]
    }
}

dp数组的定义方法

一、子序列问题

dp数组通常有两种定义方式，一维和二维，典型的例子如下所示：

1. 最长递增子序列dp[i]: 以nums[i]这个元素结尾的最长递增子序列的长度。
2. 最长回文子序列dp[i][j]: 子串s[i...j]的最长回文子序列长度。
3. 最长公共子序列dp[i][j]: 子符串s1[i...]和s2[j...]的最长公共子序列的长度。
   if (s1[i] == s2[j])
       dp[i][j] = 1 + dp[i+1][j+1]
   else
       dp[i][j] = max(dp[i][j+1], dp[i+1][j], dp[i+1][j+1])

二、打家劫舍问题

dp[i]表示从i开始抢劫，所能抢到的最多的钱。
dp[i] = max(dp[i+1], nums[i] + dp[i+2])

base case:
0 <= i < n
dp[n] = dp[n+1] = 0

三、背包问题

I 0-1背包

dp[i][w]: 前i个物品，放进容量是W的背包，可以装的最大价值。
dp[i][w] = max(dp[i-1][w], val[i]+dp[i-1][w-weight[i]])
0 <= i <= n, 0 <= w <= W
base case:
dp[0][...] = dp[...][0] = 0

经典问题：子集分割问题[LeetCode] 416. Partition Equal Subset Sum

四、股票买卖问题

• 数组定义：

dp[i][k][0 or 1]           0 <= i < n,  0 < k <= K
例如 dp[2][3][0]表示  第2天没有持有股票，至此最多进行3次交易的情况下的最大利润。

• 状态转移方程：

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]);
0 <= i < n, 0 < k <= K
base case:
dp[-1][k][0] = dp[i][0][0] = 0;
dp[-1][k][1] = dp[i][0][1] = -inf;