这篇文章上次修改于 893 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
- 最简单的动态规划类型
- 给定一个序列或网格
需要找到序列中某个/些子序列或网格中欧给你的某条路径
- 某种性质最大/最小
- 计数
- 存在性
动态规划方程 dp[i] 表示以 a[i] 结尾的满足条件的子序列性质，dpi 表示以格子 (i, j) 为结尾的满足条件的路径的性质。
- 最大值/最小值
- 个数
- 是否存在
- 空间优化：如果 dpi 只依赖当前行和前一行，则可以用滚动数组节省空间。
1 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<int>> dp(row, vector<int>(col, 0));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (obstacleGrid[i][j] == 1) {
continue;
}
if (i == 0 && j == 0) {
dp[i][j] = 1;
continue;
}
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
return dp[row - 1][col - 1];
}
};2 最长上升连续子序列
给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）
输入：[5, 4, 2, 1, 3]
输出：4
解释：
给定 [5, 4, 2, 1, 3]，其最长上升连续子序列（LICS）为 [5, 4, 2, 1]，返回 4。
class Solution {
public:
/**
* @param a: An array of Integer
* @return: an integer
*/
int longestIncreasingContinuousSubsequence(vector<int> &a) {
if (a.size() == 0) return 0;
int ans = longest(a);
reverse(a.begin(), a.end());
ans = max(ans, longest(a));
return ans;
}
int longest(vector<int> &a) {
// dp(i) = dp(i - 1) + 1 && a[i-1] < a[i]
int n = a.size();
int ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
if (a[i - 1] < a[i]) {
dp[i] = dp[i - 1] + 1;
}
if (dp[i] > ans) {
ans = dp[i];
}
}
return ans;
}
};使用滚动数组压缩空间：
class Solution {
public:
/**
* @param a: An array of Integer
* @return: an integer
*/
int longestIncreasingContinuousSubsequence(vector<int> &a) {
if (a.size() == 0) return 0;
int ans = longest(a);
reverse(a.begin(), a.end());
ans = max(ans, longest(a));
return ans;
}
int longest(vector<int> &a) {
// dp(i) = dp(i-1) + 1 && a[i-1] < a[i]
int n = a.size();
int ans = 1;
int old = 0;
int now = 1;
vector<int> dp(2, 1);
for (int i = 1; i < n; i++) {
old = now;
now = 1 - now;
if (a[i - 1] < a[i]) {
dp[now] = dp[old] + 1;
} else {
dp[now] = 1;
}
if (dp[now] > ans) {
ans = dp[now];
}
}
return ans;
}
};3 最小路径和
给定一个只含非负整数的 m∗n 网格，找到一条从左上角到右下角的可以使数字和最小的路径。
输入：
grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：
7
解释：
路线为： 1 -> 3 -> 1 -> 1 -> 1class Solution {
public:
/**
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int>> &grid) {
int row = grid.size();
if (row == 0) return 0;
int col = grid[0].size();
if (col == 0) return 0;
vector<vector<int>> dp(row, vector<int>(col));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[i][j];
continue;
}
if (i == 0) {
dp[i][j] = dp[i][j-1] + grid[i][j];
continue;
}
if (j == 0) {
dp[i][j] = dp[i-1][j] + grid[i][j];
continue;
}
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[row-1][col-1];
}
};滚动数组压缩空间：
class Solution {
public:
/**
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int>> &grid) {
int row = grid.size();
if (row == 0) return 0;
int col = grid[0].size();
if (col == 0) return 0;
vector<vector<int>> dp(2, vector<int>(col));
int now = 0;
int old = 0;
for (int i = 0; i < row; i++) {
old = now;
now = 1 - now;
for (int j = 0; j < col; j++) {
if (i == 0 && j == 0) {
dp[now][j] = grid[i][j];
continue;
}
if (i == 0) {
dp[now][j] = dp[now][j-1] + grid[i][j];
continue;
}
if (j == 0) {
dp[now][j] = dp[old][j] + grid[i][j];
continue;
}
dp[now][j] = min(dp[old][j], dp[now][j-1]) + grid[i][j];
}
}
return dp[now][col-1];
}
};4 炸弹袭击
给定一个二维矩阵, 每一个格子可能是一堵墙 W，或者 一个敌人 E 或者空 0 (数字 '0')，返回你可以用一个炸弹杀死的最大敌人数。炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。由于墙比较坚固，所以墙不会被摧毁。
输入:
grid =[
"0E00",
"E0WE",
"0E00"
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人class Solution {
public:
/**
* @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
* @return: an integer, the maximum enemies you can kill using one bomb
*/
int maxKilledEnemies(vector<vector<char>> &grid) {
int row = grid.size();
if (row == 0) return 0;
int col = grid[0].size();
if (col == 0) return 0;
vector<vector<int>> dp(row, vector<int>(col, 0));
vector<vector<int>> sum(row, vector<int>(col, 0));
int ans = 0;
// up
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 'W') {
dp[i][j] = 0;
continue;
}
dp[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (i > 0) {
dp[i][j] += dp[i-1][j];
}
sum[i][j] += dp[i][j];
}
}
// down
for (int i = row - 1; i >= 0; i--) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 'W') {
dp[i][j] = 0;
continue;
}
dp[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (i + 1 < row) {
dp[i][j] += dp[i + 1][j];
}
sum[i][j] += dp[i][j];
}
}
// left
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 'W') {
dp[i][j] = 0;
continue;
}
dp[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (j > 0) {
dp[i][j] += dp[i][j-1];
}
sum[i][j] += dp[i][j];
}
}
// right
for (int i = 0; i < row; i++) {
for (int j = col -1 ; j >= 0; j--) {
if (grid[i][j] == 'W') {
dp[i][j] = 0;
continue;
}
dp[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (j + 1 < col) {
dp[i][j] += dp[i][j+1];
}
sum[i][j] += dp[i][j];
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '0' && sum[i][j] > ans) {
ans = sum[i][j];
}
}
}
return ans;
}
};参考
https://www.bilibili.com/video/BV1nt4y1Y7n7?p=2&spm_id_from=pageDriver
没有评论