64.最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
示例 1：输入：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
分析:
1.到某个位置 [i,j] 存在最小路径重叠子问题, 定义 dp[i][j] 为到达 grid[i][j] 的最小路径和
2.dp[i][j] 可能从 2 类状态中转移过来, dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3.base 条件处理最左边和最上边
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> dp(grid);
for (int i = 1; i < row; ++i) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int i = 1; i < col; ++i) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for (int i = 1; i < row; ++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[row-1][col-1];
}
};
62.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7 输出：28
示例 2：输入：m = 3, n = 2 输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：输入：m = 7, n = 3 输出：28
示例 4：输入：m = 3, n = 3 输出：6
分析:
1.每次只能向下或者向右走一步, 对于矩阵最左边和最上边直接种类就是1, 对于中间的元素
2.因为有重叠子结构, 用 dp[i][j] 表示从起点到 [i, j] 可到的最大总数; base条件 dp[i][0] = 1 和 dp[0][j] = 1, 因为只能从[上面到下面] 和 [左边到右边]
3.对于其他的位置 dp[i][j] = dp[i-1][j] + dp[i][j-1]
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int i = 0; i < n; ++i) {
dp[0][i] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
63.不同路径II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。示例 1：输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：输入：obstacleGrid = [[0,1],[0,0]] 输出：1
分析:
1.dp[i][j] 为从 [0,0] 到 [i,j] 的路径数, 一开始默认都设置为 0
2.状态转移可以发生当且仅当当前位置不是障碍, 然后路径数可以从左边或者上面下来
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int r = obstacleGrid.size();
int c = obstacleGrid[0].size();
vector<vector<int>> dp(r, vector<int>(c, 0));
if (obstacleGrid[0][0] == 1) {
return 0;
}
dp[0][0] = 1;
for (int i = 1; i < r; ++i) {
if (dp[i-1][0] == 1 && obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
}
}
for (int i = 1; i < c; ++i) {
if (dp[0][i-1] == 1 && obstacleGrid[0][i] == 0) {
dp[0][i] = 1;
}
}
for (int i = 1; i < r; ++i) {
for (int j = 1; j < c; ++j) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
return dp[r-1][c-1];
}
};
174.地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
说明:
骑士的健康点数没有上限。任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
分析:
1.dp[i][j] 表示从 dungeon[i][j] 到 dungenon[m-1][n-1] 需要的最小健康点数, 在 dungeon在[i][j] 能走到终点的最小生命值, 应该由右边和下边的能走到终点的最小生命值推出来;
比如
A C
B
dungeon(A) = -1
dp(B) = 2
dp(C) = 3
A需要需要的是2 + (-1) = 3 这么多健康点
换一种可能性
dungeon(A) = 3
dp(B) = 2
dp(C) = 3
A需要需要的是2 - 3 = -1 这么多健康点, 但是能在A活下来, 至少需要1点健康点, 因此dp(A)必须>=1
dp[i][j] = max(min(dp[i][j+1], dp[i+1][j]) +(-dungeon[i][j]), 1)
当当前的位置处于最后一行或者最后一列的时候
dp[m-1][j] = max(dp[m-1][j+1] + (-dungeon[m-1][j]), 1)
dp[i][n-1] = max(dp[i+1][n-1] + (-dungeon[i][n-1]), 1)
这里有个技巧是, 为了避免数组越界的判断, 可以将数组开成m+1, n+1的, 然后让最右边一列和最下方一行设置成INT_MAX, 就可以把状态转移统一成一类
dp[i][j] = max(min(dp[i][j+1], dp[i+1][j]) +(-dungeon[i][j]), 1)
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
// dp[i][j]表示从dungeon[i][j]走到dp[m-1][n-1]需要的最小的健康点数;
// 防止边界条件不太好dp, 直接在最右侧和左下侧设置成INT_MAX
vector<vector<int>> dp(m+1, vector<int>(n+1));
for (int i = 0; i <= m; ++i) {
dp[i][n] = INT_MAX;
}
for (int i = 0; i <= n; ++i) {
dp[m][i] = INT_MAX;
}
// 单独处理dp[m-1][n-1]
if (dungeon[m-1][n-1] >= 0) {
dp[m-1][n-1] = 1;
} else {
dp[m-1][n-1] = (-dungeon[m-1][n-1]) + 1;
}
for (int i = m-1; i >= 0; --i) {
for (int j = n-1; j >= 0; --j) {
if (i == m-1 && j == n-1) {
continue;
}
dp[i][j] = max(min(dp[i][j+1], dp[i+1][j]) + (-dungeon[i][j]), 1);
}
}
return dp[0][0];
}
};
787.K站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。示例 1：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200
解释: 城市航班图如下
0
100 / \ 500
1 - 2
100
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。示例 2：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500
解释:
城市航班图如下
0
100 / \ 500
1 - 2
100
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
分析:
1.状态是什么? src是固定下来的, 恰好经过t次航班从 src 到达城市 i 的最小花费数, 用一个二维的数组dp[t][i]描述;
2.经过k次中转, 那么就是 dp[k+1][dst], 然后从 dp[1][dst]..dp[k+1][dst] 中找到最小的那个
3.状态转移的关系是啥? 当前状态可以由任何一个能到达城市i的城市, 经过cost(j,i)转移到当前城市i, 这种状态下的最小花费也就是 dp[t-1][j]+ cost, dp[t][i] = min(dp[t][i], dp[t-1][j] + cost(j, i)) for all j in [能到达i的所有城市集合], 到达城市i有很多个城市, 枚举这些能到城市i的城市
4.边界条件 dp[0][i] 怎么设置? 当 i == src 时 dp[0][i] = 0, 也就是说不需要任何代价; 当 i != src 时 dp[0][i] 这种状态不合法, 因为题目要找的是最小的代价, 可以设置 dp[0][i] = INT_MAX当 i！= src
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<long>> dp(k+2, vector<long>(n, INT_MAX));
dp[0][src] = 0;
for (int t = 1; t <= k+1; ++t) {
for (int idx = 0; idx < flights.size(); ++idx) {
int j = flights[idx][0];
int i = flights[idx][1];
int cost = flights[idx][2];
dp[t][i] = min(dp[t][i], dp[t-1][j] + cost);
}
}
long ans = INT_MAX;
for (int t = 1; t <= k + 1; ++t) {
ans = min(dp[t][dst], ans);
}
return (ans == INT_MAX) ? -1 : (int) ans;
}
};
741.摘樱桃
一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。示例 1: 输入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
输出: 5
解释：
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了
[
[0,1,-1],
[0,0,-1],
[0,0,0]
]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
}
};
转载请注明来源, from goldandrabbit.github.io
