手机版网站开发实例,wordpress知乎,个人网站建设论文绪论,mit网站可以做app62.不同路径
思路#xff1a;确定dp数组及其下标含义#xff0c;dp[i][j]代表到达i#xff0c;j坐标的路径数。确定递推公式dp[i][j] dp[i-1][j]dp[i][j-1]。因为只能向右向下移动。初始化dp数组#xff0c;dp数组的第一行第一列都为1#xff0c;因为不能向上向左。遍历…62.不同路径
思路确定dp数组及其下标含义dp[i][j]代表到达ij坐标的路径数。确定递推公式dp[i][j] dp[i-1][j]dp[i][j-1]。因为只能向右向下移动。初始化dp数组dp数组的第一行第一列都为1因为不能向上向左。遍历顺序从左到右从上到下因为移动方向。打印dp数组用于debug。
class Solution {
public:int uniquePaths(int m, int n) {//确定dp数组以及下标的含义 dp[i][j]表示到达i,j坐标时可以走的路径数//确定递推公式 dp[i][j] dp[i-1][j]dp[i][j-1];//初始化dp数组vectorvectorint dp(m,vectorint(n));for(int i 1;in;i){dp[0][i] 1;}for(int i 0;im;i){dp[i][0] 1;}for(int i 1;im;i){for(int j 1;jn;j){dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};
63.不同路径II
思路跟上一题不同点在于此题中具有障碍物会影响递推以及初始化在初始化过程中第一行第一列如果遇到障碍物则障碍物位置往后全部为0因为无法到达。递推时如果坐标处有障碍物直接continue让它保持初始化的0。如果起点和终点具有障碍物直接返回0算是剪枝。其他与上一题相同。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {//确定dp数组及其下标含义 dp[i][j]代表到达第ij坐标的路径数//确定递推公式 dp[i][j] dp[i-1][j]dp[i][j-1];//初始化dp数组 第一行第一列为1如果有障碍物 障碍物后为0//循环顺序从左往右 从上往下//打印dp数组用于debugint m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m,vectorint(n,0));if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1){return 0;}for(int i 0;imobstacleGrid[i][0]!1;i){dp[i][0] 1;}for(int j 0;jnobstacleGrid[0][j]!1;j){dp[0][j] 1;}for(int i 1;im;i){for(int j 1;jn;j){if(obstacleGrid[i][j]1){continue;}dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};收获
由于移动方向只能为右下因此dp数组第一行和第一列的初始化可以确定。遍历的顺序可以确定。
