简洁个人博客网站模板,网站开发的软件有哪些,淘客优惠券网站建设,用wordpress建wiki62. 不同路径
62. 不同路径 - 力扣#xff08;LeetCode#xff09; 动态规划思想第一步#xff1a;描述状态~
dp[i][j]#xff1a;表示走到i#xff0c;j位置时#xff0c;一共有多少种方法~
动态规划思想第二步#xff1a;状态转移方程~ 动态规划思想第三步#xf…
62. 不同路径
62. 不同路径 - 力扣LeetCode 动态规划思想第一步描述状态~
dp[i][j]表示走到ij位置时一共有多少种方法~
动态规划思想第二步状态转移方程~ 动态规划思想第三步初始化考虑边界情况~ 我们通过扩充数组大小可以节省初始化步骤不过需要注意下标映射关系~
动态规划思想第四步返回值~
return dp[m][n] 代码
//62 不同路径
class Solution
{
public:int uniquePaths(int m, int n){//创建dp表注意扩充vectorvectorint dp(m 1, vectorint(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(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m1,vectorint (n1));dp[0][1] 1;for(int i 1;im;i){for(int j 1;jn;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(vectorvectorint nums) {//小case,直接秒杀int m nums.size();int n nums[0].size();vectorvectorint dp(m1,vectorint(n1));for(int i 1;im;i){for(int j 1;jn;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(vectorvectorint matrix) {int m matrix.size();vectorvectorint dp(m1,vectorint(m2,INT_MAX));for(int i 0;im1;i){dp[0][i] 0;}for(int i 1;im;i){for(int j 1;jm;j){dp[i][j] min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j1]))matrix[i-1][j-1];}}int ret INT_MAX;for(int i 1;im;i){ret min(ret,dp[m][i]);}return ret;}
};
64. 最小路径和
64. 最小路径和 - 力扣LeetCode 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] 0;for(int i 1;im;i){for(int j 1;jn;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(vectorvectorint dungeon) {int m dungeon.size();int n dungeon[0].size();vectorvectorint dp(m1,vector(n1,INT_MAX));dp[m][n-1] dp[m-1][n] 1;for(int i m-1;i0;i--){for(int j n-1;j0;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];}
};
感觉讲得还不够好不够详细后面再作改善~
