中国建设银行网站评价,网站404页面在哪查看,顺的网站建设案例,企业网站开发实训目的今天更新动态规划路径问题1#xff0c;后续会继续更新其他有关动态规划的问题#xff01;动态规划的路径问题#xff0c;顾名思义#xff0c;就是和路径相关的问题。当然#xff0c;我们是从最简单的找路径开始#xff01;
动态规划的使用方法#xff1a; 1.确定状态并…今天更新动态规划路径问题1后续会继续更新其他有关动态规划的问题动态规划的路径问题顾名思义就是和路径相关的问题。当然我们是从最简单的找路径开始
动态规划的使用方法 1.确定状态并定义状态数组ij代表什么意思dp[i][j]又是什么意思 2.确定状态转移方程即递推公式 3.确定边界条件并初始化 4.确定遍历顺序 5.状态转移 6.输出结果 文章目录 一、LC 62 不同路径方法一深度优先搜索方法二动态规划二维方法三动态规划一维方法四排列组合 二、LC 63 不同路径II方法一动态规划二维方法二动态规划一维方法三记忆化搜索 三、LC 64 最小路径和方法一动态规划二维方法二动态规划一维 一、LC 62 不同路径
LC 62 不同路径 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径 方法一深度优先搜索
代码如下
class Solution {
private:int dfs(int m,int n,int i,int j){//行或列有至少一个越界if(im||jn) return 0;//到达终点(在竖直方向达到m水平方向达到n也即坐标达到m,n))if(im jn) return 1;//递归搜索左子树和右子树return dfs(m,n,i1,j)dfs(m,n,i,j1);}
public:int uniquePaths(int m, int n) {//从根节点开始遍历int cntdfs(m,n,1,1);return cnt;}
};方法二动态规划二维
代码如下
/*动态规划的使用方法
1.确定状态并定义状态数组ij代表什么意思dp[i][j]又是什么意思
2.确定状态转移方程即递推公式
3.确定边界条件并初始化
4.确定遍历顺序
5.状态转移
6.输出结果
*/
class Solution {public:int uniquePaths(int m, int n) {//定义一个状态数组用来存方法数 int dp[101][101]{0};//初始化状态数组for(int i0;im;i){dp[i][0]1;}for(int j0;jn;j){dp[0][j]1;}//遍历for(int i1;im;i){for(int j1;jn;j){//状态转移dp[i][j]dp[i][j-1]dp[i-1][j];}}//返回结果return dp[m-1][n-1];}
};方法三动态规划一维
代码如下
class Solution {
public:int uniquePaths(int m, int n) {//定义一维状态数组 int dp[101]{0};//初始化数组值为1即相对于二维数组第一行全是1for(int i0;in;i){dp[i]1;}//遍历for(int i1;im;i){for(int j1;jn;j){//状态转移dp[j]指的是上一行的j,dp[j-1]指的是当前行左边的j//每次状态转移都相当于先将上一行的运算拷贝过来再加上从左面来的方案数dp[j]dp[j-1]dp[j];}}return dp[n-1];}
};方法四排列组合
代码如下
class Solution {
public:int uniquePaths(int m, int n) {long long numerator 1; // 初始化分子int denominator m - 1; // 初始化分母int count m - 1;//定义分子的乘积项的个数int t m n - 2;//定义分子的最大乘积项while (count--) {//分子累乘count项numerator * (t--);while (denominator ! 0 numerator % denominator 0) {//约分也即除以公因数numerator / denominator;//约去一个公因数denominator--;}}return numerator;}
};二、LC 63 不同路径II
LC 63 不同路径II 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。 方法一动态规划二维
代码如下 class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {//求出二维动态数组的行数int mobstacleGrid.size();//求出二维动态数组的列数int nobstacleGrid[0].size();//定义状态数组int dp[101][101]{0};//边界判断if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1) return 0;//初始化状态数组dp[0][0]1;//遍历for(int i0;im;i){for(int j0;jn;j){//如果是障碍物则此路不通路径数归零if(obstacleGrid[i][j]1){dp[i][j]0;continue;}//状态转移此处和上面的一样if(i0 j0) dp[i][j]dp[i-1][j]dp[i][j-1];else if(i0) dp[i][j]dp[i-1][j];else if(j0) dp[i][j]dp[i][j-1];//也可以这样写
/*if(obstacleGrid[i][j]0){//状态转移此处和上面的一样if(i0 j0) dp[i][j]dp[i-1][j]dp[i][j-1];else if(i0) dp[i][j]dp[i-1][j];else if(j0) dp[i][j]dp[i][j-1];}}else continue;
*/}}return dp[m-1][n-1];}
};方法二动态规划一维
代码如下
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if (obstacleGrid[0][0] 1)return 0;vectorint dp(obstacleGrid[0].size(),0);//初始化一维状态数组第一行for (int j 0; j dp.size() obstacleGrid[0][j] 0 ; j)if (j 0)dp[j] 1;elsedp[j] dp[j-1];//for (int i 1; i obstacleGrid.size(); i)//行for (int j 0; j dp.size(); j){//列if (obstacleGrid[i][j] 1)dp[j] 0;else if (j ! 0)dp[j] dp[j] dp[j-1];}return dp.back();//返回最后一个状态对应值}
};方法三记忆化搜索
代码如下
class Solution {
public:int m,n;vectorvectorintmemo;vectorpairint,intdir{{0,1},{1,0}};int uniquePathsWithObstacles(vectorvectorint ob) {nob.size();mob[0].size();if(ob[0][0]1||ob[n-1][m-1]1){return 0;}memo.resize(n,vectorint(m,0));return dfs(ob,0,0);}int dfs(vectorvectorintob,int i,int j){if(memo[i][j]!0){return memo[i][j];}if(in-1jm-1){memo[i][j]1;return 1;}int cur0;for(auto d:dir){int xid.first;int yjd.second;if(x0xny0ymob[x][y]0){curdfs(ob,x,y);}}memo[i][j]cur;return memo[i][j];}
};作者Gallant MurdockrFZ
链接https://leetcode.cn/problems/unique-paths-ii/solutions/2466610/dfsji-yi-hua-sou-suo-by-gallant-murdockr-e882/
来源力扣LeetCode 三、LC 64 最小路径和
LC 64 最小路径和 给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。 方法一动态规划二维
代码如下
class Solution {
public:int minPathSum(vectorvectorint grid) {//定义一个二维状态数组int dp[201][201]{0};//初始化状态数组dp[0][0]grid[0][0];//获得行数和列数int mgrid.size();int ngrid[0].size();for(int i0;im;i){for(int j0;jn;j){//正常情况if(i0 j0){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j];}//边界条件else if(i0) dp[i][j]dp[i-1][j]grid[i][j];else if(j0) dp[i][j]dp[i][j-1]grid[i][j];}}return dp[m-1][n-1];}
};方法二动态规划一维
代码如下
class Solution {
public:int minPathSum(vectorvectorint grid) {//获取行数和列数int mgrid.size();int ngrid[0].size();//定义一维状态数组int dp[201]{0};//初始化第一行dp[0]grid[0][0];for(int i1;in;i){dp[i]grid[0][i]dp[i-1];}//状态转移配合滚动数组优化for(int i1;im;i){for(int j0;jn;j){//左边界if(j0) dp[j]grid[i][j];//其他情况else dp[j]min(dp[j-1],dp[j])grid[i][j];}}return dp[n-1];}
};我以前没怎么接触过动态规划目前就是每天有空看看题想想解题思路啥的但愿有效果吧
