我爱学算法之——动态规划（三）

一、下降路径最小和题目解析给定一个 m*n 的矩阵从第一行任意一个元素开始从每一行选择一个元素下一行与当前行选择的元素最多只能相隔一列即对于[i,j]下一行选择的元素应该是[i1,j-1]或者[i1,j]或者[i1,j1]求下降路径的最小和算法思路状态表示dp[i][j]表示 从第一行下降到[i,j]位置的下降路径的最小值状态转移方程对于任意位置[i,j]上一行都可能选择j-1、j、j1列所以状态转移方程 dp[i][j] max(max(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j1]) matrix[i-1][j-1]初始化在填表过程当中填dp[i][j]时会用到dp[i-1][j-1]、dp[i-1][j]、dp[i-1][j1]这里在创建 dp 表时就多创建一行、两列第 0 行初始化为0第 0 列和第 n1 列 初始化为 10000 (比较大的值不影响结果即可)返回值这里要求的是下降路径的最小值最终结果就应该是dp 表 第 m 行的最小值代码实现classSolution{public:intminFallingPathSum(vectorvectorintmatrix){intmmatrix.size();intnmatrix[0].size();vectorvectorintdp(m2,vectorint(n2,10000));for(inti0;in2;i)dp[0][i]0;for(inti1;im;i){for(intj1;jn;j){dp[i][j]min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j1])matrix[i-1][j-1];}}intret10000;for(inti1;in;i)retmin(ret,dp[m][i]);returnret;}};二、最小路径和题目解析给定一个二维数组从左上角开始每次只能向下或者向右移动一步。求从左上角到右下角的所有路径中路径数字总和的最小值。算法思路状态表示dp[i][j]表示 从 左上角 到[i,j]位置的所有路径中路径数字总和的最小值。状态转移方程dp[i][j] min(dp[i-1][j],dp[i][j-1]) grid[i][j]初始化这里 dp 表创建m*n和grid表一样初始化第一行和第一列即可。返回值左上角到右下角的路径数字总和的最小值最终结果存储在dp[m-1][n-1]当中代码实现classSolution{public:intminPathSum(vectorvectorintgrid){intmgrid.size();intngrid[0].size();vectorvectorintdp(m,vectorint(n,0));dp[0][0]grid[0][0];for(inti1;im;i)dp[i][0]dp[i-1][0]grid[i][0];for(inti1;in;i)dp[0][i]dp[0][i-1]grid[0][i];for(inti1;im;i)for(intj1;jn;j)dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j];returndp[m-1][n-1];}};三、地下城游戏题目解析给定一个地下城矩阵 dungeondungeon[i][j]表示进入该位置的代价负数表示损失健康点数整数表示恢复健康点数骑士在左上角每次只能向右或者向下移动一格当骑士生命值将至 0 时骑士就会立即死亡求骑士能够走到右下角拯救公主的最低初始健康点数算法思路这道题用以往的状态表示以 某个位置为结尾 … 会发现找不出来状态转移方程因为从[i,j]位置走到 右下角的最低健康值不知道。所以这道题状态表示dp[i][j]表示 以[i,j]为起点能走到右下角的最低初始健康值从终点出发一步步计算每个位置最少需要多少血才能走到终点状态表示dp[i][j]表示以[i,j]位置为起点能走到右下角的最低初始健康值。状态转移方程已知dp[i1][j]、dp[i][j1]以[i1,j]、[i,j1]为起点能走到右下角的最低初始健康值以及dungeon[i][jj]从[i,j]位置为起点能走到右下角位置存在大小关系 dp[i][j] dungeon[i][j] min(dp[i1][j] , dp[i][j1])要求最小初识健康值那么状态转移方程dp[i][j] max(min(dp[i1][j],dp[i][j1]) - dungeon,1)注意在任意时刻健康值降至 0 骑士就立即死亡了所以dp[i][j]的值不能小于 1初始化这道题就要倒着推这里就虚拟出一行一列初始值为 0x3f3f3f较大的值不影响最终结果即可而dp[m][n-1]或者dp[m-1][n]右下角的下一步位置这里就初始化为 1返回值求的是 从左上角 到右下角的最低初始健康值最终结果就存储在dp[0][0]中代码实现classSolution{public:intcalculateMinimumHP(vectorvectorintdungeon){intmdungeon.size();intndungeon[0].size();vectorvectorintdp(m2,vectorint(n2,0x3f3f3f));dp[m][n-1]1;for(intim-1;i0;i--){for(intjn-1;j0;j--){dp[i][j]max(min(dp[i1][j],dp[i][j1])-dungeon[i][j],1);}}returndp[0][0];}};本篇文章到这里就结束了感谢支持我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code2oul0hvapjsws