网站报价文档,网站备案 新闻类前置审批,什么是网络营销战略,山东最新消息文章目录 931. 下降路径最小和算法原理代码实现 64. 最小路径和算法原理代码实现 174. 地下城游戏算法原理代码实现 931. 下降路径最小和
题目链接#xff1a;931. 下降路径最小和
算法原理 状态表示#xff1a; 经验题目要求#xff1a;dp[i][j]表示到达[i,j]位置时… 文章目录 931. 下降路径最小和算法原理代码实现 64. 最小路径和算法原理代码实现 174. 地下城游戏算法原理代码实现 931. 下降路径最小和
题目链接931. 下降路径最小和
算法原理 状态表示 经验题目要求dp[i][j]表示到达[i,j]位置时最小的下降路径 状态转移转移方程 根据最近的一步划分问题 初始化 状态转移方程会用到左中右三个位置所以我们可以往外扩一圈这样就不需要担心越界的问题 这因为是最小值加上当前值所以第一行全部设置为0不会影响元素表格第一行初始化 然后其他的设置为∞即可不会影响结果 **填表顺序**从上往下 **返回值**最后一行最小值
代码实现
class Solution {
public:int minFallingPathSum(vectorvectorint matrix){int n matrix.size();vectorvectorint dp(n1, vectorint(n2, INT_MAX));//初始化for(int j 0; j n2; j) dp[0][j] 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][j1])) matrix[i-1][j-1];}} int ret INT_MAX;for(int j 1; j n; j){ret min(ret, dp[n][j]);}return ret;}
};64. 最小路径和
题目链接64. 最小路径和
算法原理
感觉和上一篇文章的题目一样只不过加了个选择最小的直接看代码吧 代码实现
class Solution {
public:int minPathSum(vectorvectorint grid){int m grid.size();int n grid[0].size();vectorvectorint dp(m1, vectorint(n1, INT_MAX));//初始化dp[0][1] dp[1][0] 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];}
};174. 地下城游戏
题目链接174. 地下城游戏
算法原理
有点像小时候玩的按键设计的魔塔游戏。 **状态表示**这里就不是以某个位置为结尾的xxx了因为这个状态不仅受到前面的影响还受到后面的影响。 所以用以某个位置为起点的xxxdp[i][j]表示从[i, j]位置出发到达终点所需的最低初始健康点数 状态转移方程 假设以[i,j]位置为起点走到终点它可以往下或者往右走 假设此时dp[i][j]为x要走到下一步最起码要大于或等于下个位置的最低血量 然后两种情况取较小的即可 Tips 此时[i, j]位置可能是一个加血包如果太大就会是负数了这样就符合逻辑所以还需要比较一下
代码实现
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon){int m dungeon.size();int n dungeon[0].size();vectorvectorint dp(m1, vectorint(n1, 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[i1][j], dp[i][j1]) - dungeon[i][j];dp[i][j] max(1, dp[i][j]);}} return dp[0][0];}
};
