目录
路径问题
1.第一题
画图分析
动态规划解题的几步
1.确定状态表示
根据经验+题目要求
dp[i][j]表示走到[i,j]位置时的不同路径数
2.状态转移方程
以当前[i,j]位置状态的最近一步来划分子问题，将每个子问题用状态表示，即表示为dp[x][y]
3.初始化
4.填表顺序
从上往下填写每一行，每一行从左往右
5.返回值 dp[m][n](最右下位置)
具体代码
int uniquePaths(int m, int n)
{
//1.创建dp表
//2.初始化
//3.填表
//4.返回值
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];
}2.第二题
画图分析:
使用动态规划来解决
1.确定状态表示
和上题一样dp[i][j]表示走到[i,j]位置时的不同路径数
2.状态转移方程
3.初始化 与上题一样
4.调表顺序 从上往下填写每一行，每一行从左往右
5.返回值 dp[m][n]
具体代码：
int uniquePathsWithObstacles(vector<vector<int>>& ob)
{
int m=ob.size(),n=ob[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
dp[1][0]=1;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
if(ob[i-1][j-1]==0)//注意下标的映射关系
dp[i][j]=dp[i-1][j]+dp[i][j-1];
return dp[m][n];
}3.第三题
OJ传送门 LeetCode<LCR 166>珠宝的最高价值
画图分析
使用动态规划解决问题：
1.确定状态表示： 根据经验+题目要求
dp[i][j]表示到达[i,j]位置时的最高价值
2.状态转移方程
3.初始化
4.填表顺序 从上往下填写每一行，每一行从左往右进行填写
5.返回值 dp[m][n]
具体代码
int jewelleryValue(vector<vector<int>>& frame)
{
int m=frame.size(),n=frame[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多加了一行和一列，原数组访问需要注意下标的映射关系
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
return dp[m][n];
}4.第四题
画图分析
使用动态规划解决问题
1.确定状态表示 根据经验+题目要求
dp[i][j]表示到达[i,j]位置时的最小路径和
2.状态转移方程
3.初始化
4.填表顺序 从上到下
5.返回值
因为题目要求是到最后一行都是结束位置，只需返回最后一行的最小值就行
具体代码：
int minFallingPathSum(vector<vector<int>>& matrix)
{
int n=matrix.size();
vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
//对第一行初始化为0
for(int i=0;i<n+2;++i)
dp[0][i]=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))
+matrix[i-1][j-1];//注意下标的映射关系
int ret=INT_MAX;
for(int i=1;i<=n;++i)
ret=min(ret,dp[n][i]);
return ret;
}5.第五题
画图分析：
使用动态规划解决问题
1.确定状态表示 根据经验+题目要求
dp[i][j]表示到[i,j]时的最小路径和
2.状态转移方程 以最近的一步划分子问题
3.初始化
4.填表顺序 从上往下，从左往右
5.返回值 dp[m][n]
具体代码
int minPathSum(vector<vector<int>>& grid)
{
int m=grid.size(),n=grid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
dp[1][0]=dp[0][1]=0;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
return dp[m][n];
}6.第六题
画图分析：
使用动态规划解决问题
1.确定状态表示 根据经验+题目要求
若dp[i][j]表示:从起点出发走到[i,j]位置时所需的最小健康点数
可以看出上面的状态表示无法推导出状态转移方程，我们可以换一种状态表示的方式
dp[i][j]表示从[i,j]位置出发，到达终点时，所需的最小健康数
2.状态转移方程
3.初始化
4.填写顺序
从下往上填写每一行，从右往左
5.返回值 dp[0][0]
具体代码：
int calculateMinimumHP(vector<vector<int>>& d)
{
int m=d.size(),n=d[0].size();
vector<vector<int>> dp(m+1,vector<int>(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])-d[i][j];
dp[i][j]=max(1,dp[i][j]);
}
return dp[0][0];
}