网站建设页面大小,wordpress readd,wordpress自定义文章列表,德州手机网站建设服务题目链接#xff1a;leetcode不同路径 目录
题目解析#xff1a;
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析#xff1a; 题目让我们求总共有多少条不同的路径可到达右下角#xff1b;
由题可得#xff1a;
机器人位于…题目链接leetcode不同路径 目录
题目解析
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析 题目让我们求总共有多少条不同的路径可到达右下角
由题可得
机器人位于一个 m x n 网格
机器人每次只能向下或者向右移动一步 我们拿示例2来分析 则根据题目要求我们只能向下或者向右移动一步不能向上或向左回退
所以这里我们一共有三种走法 算法原理:
1.状态表示
根据题目要求先创建一个 m x n 大小的dp表 首先先思考dp表里面的值所表示的含义是什么
dp[i][j]表示到达i*j时一共有多少种方式 这种状态表示怎么来的
1.经验题目要求
经验以i*j位置为结尾
题目让我们求到达右下角有多少种方式那么这里我们可以dp[i][j]来表示。
所以这里我们用i*j表示右下角位置 2.状态转移方程
dp[i][j]等于什么
用之前或者之后的状态推导出dp[i][j]的值
根据最近的最近的一步来划分问题 当机器人到达dp[i-1][j]时我们知道它到达[i-1][j]有dp[i-1][j]方式
此时只需要从[i-1][j]往下走一步就可以到达目标位置即
……--[i-1][j]--(往下走一步)[i][j]
……--[i-1][j]--(往下走一步)[i][j]
……--[i-1][j]--(往下走一步)[i][j]
……
所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种 那么同理
当机器人到达dp[i][j-1]时我们知道它到达[i][j-1]有dp[i][j-1]方式
此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置即
……--[i][j-1]--(往右边走一步)[i][j]
……--[i][j-1]--(往右边走一步)[i][j]
……--[i][j-1]--(往右边走一步)[i][j]
……
所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种 综上所述我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到到达[i][j]位置的总方法
即
dp[i][j]dp[i-1][j]dp[i][j-1]; 3.初始化
(保证填表的时候不越界)
由我们的状态转移方程得
在0行0列的时候越界所以我们这里可以在m*n的外围多加1行1列如图 还有一个问题是
我们要拿新增用来初始化的行和列要初始化为几呢
假设如果所需要到达的位置就在机器人所在的位置此时有一种方式
根据状态转移方程在[0][1]与[1][0]位置要有一个位置需要初始化为1其他位置初始化为0
我们这里选择[0][1]初始化为1 4.填表顺序
为了填写当前状态的时候所需要的状态已经计算过了
这里所需要的状态是到达该位置的上面和左边位置的方式
所以填表顺序
从上到下填写每一行
从左到右填写每一列
5.返回值
根据题目要求和状态表示
综上分析
返回值为dp[m][n]; 编写代码: class Solution {
public:int uniquePaths(int m, int n) {//1.创建dp表//2.初始化//3.填表//4.返回结果vectorvectorint dp(m 1, vectorint(n 1, 0));dp[0][1]1;for(int i1;im1;i)for(int j1;jn1;j)dp[i][j]dp[i][j-1]dp[i-1][j];return dp[m][n];}
};
