62. 不同路径
62. 不同路径 - 力扣（LeetCode）
动态规划思想第一步：描述状态~
dp[i][j]：表示走到i，j位置时，一共有多少种方法~
动态规划思想第二步：状态转移方程~
动态规划思想第三步：初始化（考虑边界情况）~
我们通过扩充数组大小可以节省初始化步骤，不过需要注意下标映射关系~
动态规划思想第四步：返回值~
return dp[m][n]
代码
//62 不同路径
class Solution
{
public:
int uniquePaths(int m, int n)
{
//创建dp表（注意扩充）
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//细节处理
dp[0][1] = 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][n];
}
};其实动态规划核心就在于初始化和状态转移方程，之所以初始化主要考虑的就是填表边界情况，把特殊情况考虑了才方便让dp表一次到位。而状态转移方程尤其需要注意最近一步，一定得分析是如何到这一步的~
63. 不同路径 II
63. 不同路径 II - 力扣（LeetCode）
其实本道题跟上一道一样，唯一要注意的就是判定有无障碍物挡路~
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int> (n+1));
dp[0][1] = 1;
for(int i = 1;i<=m;i++)
{
for(int j = 1;j<=n;j++)
{
//小细节：dp表与原数组是对应不上的
if(obstacleGrid[i-1][j-1]==0)
{
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[m][n];
}
};代码就是在上一道题的基础上多了一步判断，由于我们的dp表与原数组不是同等大小了，所以要记得对应位置的映射。
LCR 166. 珠宝的最高价值
LCR 166. 珠宝的最高价值 - 力扣（LeetCode）
也练习挺多道的了，这道题甚至感觉不用画图，就照着前面的套路添加一个判断大小即可~
class Solution {
public:
int jewelleryValue(vector<vector<int>>& nums) {
//小case,直接秒杀
int m = nums.size();
int n = nums[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i = 1;i<=m;i++)
{
for(int j = 1;j<=n;j++)
{
dp[i][j] = nums[i-1][j-1]+max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
};931. 下降路径最小和
931. 下降路径最小和 - 力扣（LeetCode）
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size();
vector<vector<int>> dp(m+1,vector<int>(m+2,INT_MAX));
for(int i = 0;i<=m+1;i++)
{
dp[0][i] = 0;
}
for(int i = 1;i<=m;i++)
{
for(int j = 1;j<=m;j++)
{
dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i-1][j-1];
}
}
int ret = INT_MAX;
for(int i = 1;i<=m;i++)
{
ret = min(ret,dp[m][i]);
}
return ret;
}
};64. 最小路径和
64. 最小路径和 - 力扣（LeetCode）
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//秒杀，分析越来越快了~
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
dp[0][1] = 0;
for(int i = 1;i<=m;i++)
{
for(int j = 1;j<=n;j++)
{
dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];
}
}
return dp[m][n];
}
};
174. 地下城游戏
174. 地下城游戏 - 力扣（LeetCode）
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector<vector<int>> dp(m+1,vector(n+1,INT_MAX));
dp[m][n-1] = dp[m-1][n] = 1;
for(int i = m-1;i>=0;i--)
{
for(int j = n-1;j>=0;j--)
{
dp[i][j] = min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
dp[i][j] = max(1,dp[i][j]);
}
}
return dp[0][0];
}
};感觉讲得还不够好，不够详细，后面再作改善~
