LeetCode——动态规划

动态规划

一、一维数组：斐波那契数列

爬楼梯70简单

dp定义： dp[i]表示爬到第i阶有多少种不同的方式

状态转移方程： dp[i] = dp[i-1] + dp[i-1] （每次可以爬1或2个台阶）

边界条件： dp[0] = 1; dp[1] = 1;（满足dp[2] = 2）

返回值： dp[n]，即通过累积，dp[n]为爬到第n阶台阶的方式

改进： 因为dp只使用了前两个值，所以使用两个变量存储两个值，不断迭代更新。——试过之后与原dp数组相比改进不大，可能是因为题中n的值比较小，如果n的值较大的话，会节省空间开销。
打家劫舍198中等

dp定义： dp[i]表示打劫到第i间房屋能偷窃到的最高金额

状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + 第i间房屋的金额)

边界条件： dp[0] = 0; dp[1] = nums[0]; (后续要计算dp[i-2])

返回值： dp[n]，即打劫到第n间房屋能偷窃到的最高金额

改进： 同样可以缩小空间开销，在数组够长的时候可以进行节省。
打家劫舍Ⅱ213中等

该题在上一题的基础上加了一个限制条件，房屋是环形，也就是在偷了第一间房的情况下不能偷最后一间；偷了最后一间的情况下不能偷第一间！！ 所以分为两种情况，从第1间到第n-1间，从第2间到第n间。

dp定义： dp[i]表示打劫到第i间房屋能偷窃到的最高金额

状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + 第i间房屋的金额)

边界条件： 只有一间房屋，返回该房屋的金额；只有两间房屋，返回两间房屋中金额最大的；超过两间，根据特殊情况分别计算抢劫第1间房屋和最后一间房屋两种情况下能获取到的最高金额，将其返回。

返回值： 盗窃金额最高的情况

改进： 节省空间开销

总结：以上情况均使用了一维dp数组，且状态转移方程与数组的前几个数有关，可以使用变量存储，节省空间开销。关键对dp[i]的定义明确，状态转移方程确定好，在这种情况下再对边界情况进行特殊考虑。

二、二维数组：矩阵路径

矩阵的最小路径和64中等

dp定义： dp[i][j]表示移动到[i][j]位置的时候路径上的数字和最小

状态转移方程： dp[i][j] = min(dp[i-1][j] + [i][j]位置的数字, dp[i][j-1] + [i][j]位置的数字)

边界条件： 第一行+[i][j-1], 第一列+[i-1][j]

返回值： dp[m][n]

题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：输入：grid = [[1,2,3],[4,5,6]]
输出：12

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int raw = grid.size();int col = grid[0].size();vector<vector<int>> dp(raw, vector<int>(col, 0));dp[0][0] = grid[0][0];for (int j = 1; j < col; j++) {dp[0][j] = dp[0][j-1] + grid[0][j];}for (int i = 1; i < raw; i++) {dp[i][0] = dp[i-1][0] + grid[i][0];}// 遍历for (int i = 1; i < raw; i++) {for (int j = 1; j < col; j++) {dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[raw-1][col-1];}
};

改进： 空间优化，相当于对矩阵进行了压缩

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int raw = grid.size();int col = grid[0].size();vector<int> dp(col);// 初始化dp[0] = grid[0][0];for (int i = 1; i < col; i++) {dp[i] = dp[i-1] + grid[0][i];}for (int i = 1; i < raw; i++) {dp[0] = dp[0] + grid[i][0];for (int j = 1; j < col; j++) {dp[j] = min(dp[j-1] + grid[i][j], dp[j] + grid[i][j]);}}return dp[col-1];}
};

不同路径62中等

dp定义： dp[i][j]表示到[i][j]位置的路径总数

状态转移方程： dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件： dp[0][j] = 1; dp[i][0] = 1

返回值： dp[m-1][n-1]

改进： 和上一题一样的思路

三、数组区间

四、分割整数

分割整数的最大乘积343

dp定义： dp[i] 表示第i个数拆分后可以得到的最大乘积，会成为后面数的因数。

状态转移方程： i表示当前要计算最大乘积的数，j表示i的某个因数
```
for (int i = 2; i <= n; i++) {int curMax = 0;for (int j = 1; j < i; j++) {curMax = max(curMax, max(j* (i-j), j * dp[i-j]));}dp[i] = curMax;
}
```
边界条件： 拆分的正整数的个数大于2，所以dp[0] = 0; dp[1] = 1

返回值： dp[n]

改进：
按平方数来分割整数279中等
dp定义： dp[i]表示i的完全平方数的最小数量

状态转移方程：
```
for (int i = 1; i <= n; i++) {int minValue = INT_MAX;for (int j = 1; j * j <= i; j++) {minValue = min(minValue, dp[i-j*j]);}dp[i] = minValue + 1;
}
```
边界条件： dp[0] = 0

返回值： dp[n]

改进：
分割整数构成字母字符串91中等
dp定义： dp[i]表示0-i位置有的编码方式

状态转移方程： 因为26个字母编码有两位数，而且前缀0是不能包含在两位数的，所以分为两种情况：

第一种是只把加第i个数当成编码：
```
if (s[i-1] != '0') {dp[i] += dp[i-1];}
```
第二种加上前一个数看是否构成新的编码：
```
if (s[i-2] != 0 && ((s[i-2] - '0') * 10 + (s[i-1] - '0')) < 26) {dp[i] += dp[i-2];
}
```
边界条件： dp[0] = 1;

返回值： dp[n]

改进：

五、最长递增子序列

最长递增子序列300中等

dp定义： dp[i]表示从0-i可以构成递增子序列的最大长度

状态转移方程： 因为可以删除数组中的某些元素，所以递增子序列要从之前的所有数检查。
```
for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = i - 1; j>= 0; j--) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}
}
```
边界条件： dp[i] = 1，每个元素都是一个递增子序列

返回值： dp数组中的最大值。

改进： 贪心+二分查找

贪心：因为我们想要上升子序列尽可能长，所以就要序列上升得尽可能慢，每次在上升子序列最后加上的数尽可能小

dp定义：dp[i]表示长度为i的最长上升子序列的末尾元素的最小值，用len记录目前最长上升子序列的长度，起始为1

状态转移方程：
```
if (nums[i] > d[len]) {d[++len] = nums[i];
} else {// 二分查找int l = 1, r = len, pos = 0;while (l <= r) {int mid = (l + r) >> 1;if (d[mid] < nums[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nusm[i];-0
} 
```
边界条件：dp[1] = nums[0];

返回值：len
一组整数对能够构成的最长链646中等
dp定义： dp[i]表示以pairs[i]为结尾的最长数对链的长度

状态转移方程： 先将数对链的第一个元素进行排序，以第i位为定点，遍历之前一共可以组成多少个数对链
```
sort(pairs.begin(), pairs.end());
for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (pairs[i][0] > pairs[j][1]) {dp[i] = max(dp[i], dp[j] + 1);}}
}
```
边界条件： 无

返回值： dp[n-1]

改进： 按元组的第二个数的大小进行排序

最长摆动子序列376中等

dp定义： 两个dp分别定义上升序列up和下降序列down

状态转移方程：

如果差是正，up序列更新，如果差是负，down序列更新，如果差为0都不更新。

up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {if (nums[i] > nums[i-1]) {up[i] = max(up[i-1], down[i-1] + 1);down[i] = down[i-1];} else if (nums[i] < nums[i-1]) {down[i] = max(down[i-1], up[i-1] + 1);up[i] = up[i-1];} else {up[i] = up[i-1];down[i] = down[i-1];}
}

边界条件： up[0] = down[0] = 1;

返回值： max(down[i-1], up[i-1]);

改进： 减少空间消耗，使用up和down两个变量进行存储

int up = 1, dowm = 1
for (int i = 1; i < n; i++) {if (nums[i] - nums[i-1] > 0) {down += 1;} else if (nums[i] - nums[i-1] < 0){up += 1;}
}
return max(up, down);

六、最长公共子序列

最长公共子序列1143中等

dp定义： dp[i][j]表示word1的第i位和word2的第j位之前序列的最长公共子序列

状态转移方程：

如果word1[i] == word2[j], dp[i][j] = dp[i-1][j-1] + 1

如果word1[i] != word2[j], dp[i][j] = max(dp[i-1][j], dp[i][j-1])

边界条件： dp[0][0] = 0

返回值： dp[n][m]

改进：

七、0-1背包

组合总和377组合总和Ⅳ

dp定义： dp[i] 表示和为i时的元素组合个数

状态转移方程：

for(int i = 1; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {if (i >= nums[j] && dp[i - nums[j]] < INT_MAX - dp[i]) {dp[i] += dp[i - nums[j]];}}
}

边界条件： dp[0] = 1

返回值： dp[target]

改进：

八、股票交易

允许的交易次数

能否在同一天进行买卖

增加限制条件要增加维度

股票交易Ⅰ 121简单
dp定义： 最简单的情况，只有一个限制是不能在同一天进行买卖，只进行一次交易，dp[i]表示第i天卖出能获得的最大利润

状态转移方程：

dp[i] = max(dp[i-1], prices[i] + minprices)

边界条件：

dp[0] = 0;

返回值： dp[n]

改进： 空间优化，两个变量buy和sell分别保存
```
int buy = -prices[0];
int sell = 0;
for (int i = 1; i < n; i++) {buy = max(buy, -prices[i]);sell = max(sell, buy + prices[i]);
}
```

股票交易Ⅱ 122中等

没有限制交易次数

可以在同一天进行买卖

dp定义： dp[i][j]表示第i天的买入（j=0）可以获得的最大利润和第i天卖出（j=1）可以获得的最大利润

状态转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

边界条件：

dp[0][0] = -prices[0];

dp[0][1] = 0;

返回值： dp[n-1][1]

改进： 空间优化

int buy = -prices[0];
int sell = 0;
for (int i = 1; i < n; i++) {// int temp_buy = max(buy, sell - prices[i]);// int temp_sell = max(sell, buy + prices[i]);// buy = temp_buy;// sell = temp_sell;// 第二种// int temp_buy = buy;// int temp_sell = sell;// buy = max(temp_buy, temp_sell - prices[i]);// sell = max(temp_sell, temp_buy + prices[i]);// 第三种buy = max(buy, sell - prices[i]);sell = max(sell, buy + prices[i]);
}
return sell;

股票交易Ⅲ123困难
两次交易

允许同一天买卖

dp定义： dp[i][j]表示第i天的利润，j=0表示第一次买入；j=1表示第一次卖出；j=2表示第二次买入；j=3表示第二次卖出

状态转移方程：

dp[i][0] = max(dp[i-1][0], -prices[i]);

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);

dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);

边界条件：

dp[0][0] = -prices[0];

dp[0][2] = -prices[0];

返回值： dp[n-1][3]

改进： 空间优化
```
for (int i = 1; i < n; i++) {// 第一种// int temp_buy1 = buy1;// int temp_sell1 = sell1;// int temp_buy2 = buy2;// int temp_sell2 = sell2;// buy1 = max(temp_buy1, -prices[i]);// sell1 = max(temp_sell1, temp_buy1 + prices[i]);// buy2 = max(temp_buy2, temp_sell1 - prices[i]);// sell2 = max(temp_sell2, temp_buy2 + prices[i]);// 第二种buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]);
}
```

股票交易Ⅳ188困难

K次交易

允许同一天进行买卖

dp定义： 定义dp数组，i表示第i天，k表示完成了k次交易，j有两个状态，1表示手中持有股票，0表示手中没有股票

状态转移方程：

// 状态转移
for (int i = 1; i < n; i++) {for (int K = 1; K <= k; K++) {dp[i][K][0] = max(dp[i-1][K][0], dp[i-1][K-1][1] + prices[i]);dp[i][K][1] = max(dp[i-1][K][1], dp[i-1][K][0] - prices[i]);}
}

边界条件：

// 初始化
for (int i = 0; i <= k; i++) {dp[0][i][0] = 0;dp[0][i][1] = -prices[0];
}
for (int i = 1; i < n; i++) {dp[i][0][0] = 0;dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][0] - prices[i]);
}

返回值： dp[n-1][k][0]

改进：

九、字符串编辑

1. 删除两个字符串的字符使他们相等583

本质：二维DP

dp定义： dp[i][j]表示word1的i位置和word2的j位置最长公共子序列的长度，删除操作数为两个字符串的长度和减去两倍最长公共子序列的长度

状态转移方程：

if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;
} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

边界条件： dp[0][j] = 0; dp[i][0] = 0;

返回值： (n + m) - 2 * dp[n][m]

改进：

2. 编辑距离72困难

dp定义： dp[i][j]表示word1的第i个位置与word2的第j个位置相同的话需要的最少操作数，行表示插入，列表示删除，对角线表示

状态转移方程：

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

边界条件： dp[i][0] = i，表示删除；dp[0][j] = j，表示插入。

返回值： dp[n][m]

改进：

3. 复制粘贴字符650中等

dp定义： dp[i]表示能够打印i个’A’的最少操作次数

状态转移方程：

for (int i = 2; i <= n; i++) {dp[i] = INT_MAX;for (int j = 1; j * j <= i; j++) {if (i % j == 0) {dp[i] = min(dp[i], min(dp[i / j] + j, dp[j] + i / j));}}
}

边界条件： dp[1] = 0

返回值： dp[n]

改进：