力扣 不同路径（动态规划）（ACM模式详解）_力扣acm模式在哪

题目描述力扣 62.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7

输出：28

示例 2：

输入：m = 3, n = 2

输出：3

解释：

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右

3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3

输出：28

示例 4：

输入：m = 3, n = 3

输出：6

思路

1.确定dp数组（dp table）以及下标的含义

根据题意，需要一个二维数组dp来表示

则dp[i][j]表示的是到达[i][j]的位置有dp[i][j]种方法

2.确定递推公式

每次只能向右或者向下移动，因此[i][j]的位置由[i-1][j]和[i][j-1]移动得到，因此移动的步数dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.dp数组如何初始化

由题意可知，第1行和第1列必须先初始化，才能推出其他位置

因此第1行和第1列都初始化为1

4.确定遍历顺序

从左上角递推得到右下角，则遍历顺序为从左到右，从上到下

5.举例推导dp数组

完整代码如下（ACM模式）

#include<iostream>
#include<vector> 
using namespace std; 
 
// 1.确定dp数组（dp table）以及下标的含义
// 2.确定递推公式
// 3.dp数组如何初始化
// 4.确定遍历顺序
// 5.举例推导dp数组
 
class Solution {
public:
    int uniquePaths(int m, int n) {
        //1.dp数组含义 到达[i][j]位置有dp[i][j]种方法
        vector<vector<int>> dp(m,vector<int>(n,0));//定义dp数组，全部初始化为0
 
        // 3.dp数组如何初始化
        //初始化dp数组，第0行为1
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
 
 
        //初始化dp数组，第0列为1
        for(int j=0;j<n;j++){
            dp[0][j]=1;
        }
 
        // 4.确定遍历顺序
        //遍历p数组，顺序为从上到下，从左到右
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];//2.确定递推公式
            }
        }
 
        return dp[m-1][n-1];
 
    }
};
 
int main(){
    int m,n;
    cin>>m>>n;
    
    Solution solution;
    int r=solution.uniquePaths(m,n);
    cout<<r<<endl;
}

---

题目描述力扣 63.不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

输出：2

解释：3x3 网格的正中间有一个障碍物。

从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]

输出：1

思路

与力扣 62.不同路径 不同的是加入了障碍物，因此初始化的时候障碍物后的格子不进行初始化，遍历时，遇到障碍物则跳过

注意

新建的dp数组是一个全0数组，迭代的结果也在上面输入，因此每次对比obstacleGrid数组来看该位置是否有障碍物，若没有则存入dp[i][j]，若有则跳过

完整代码如下（ACM模式）

#include<iostream>
#include<vector> 
using namespace std; 
 
// 1.确定dp数组（dp table）以及下标的含义
// 2.确定递推公式
// 3.dp数组如何初始化
// 4.确定遍历顺序
// 5.举例推导dp数组
 
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        
        vector<vector<int>> dp(m,vector<int>(n,0));
 
        //如果起点或终点放了障碍物，则不可能到达，因此路径为0
        if(obstacleGrid[m-1][n-1]==1 || obstacleGrid[0][0]==1){
            return 0;
        }
 
        //初始化第1行，若第1行有障碍物则障碍物后面格子不初始化
        for(int j=0;j<n && obstacleGrid[0][j]==0;j++){
            dp[0][j]=1;
        }
 
         //初始化第1列，若第1列有障碍物则障碍物后面格子不初始化
        for(int i=0;i<m && obstacleGrid[i][0]==0;i++){
            dp[i][0]=1;
        }
 
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1){//当该格没有障碍物时
                    continue;
                }
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
 
        return dp[m-1][n-1];
    }
};
 
int main(){
    vector<int> vec;
    vector<vector<int>> obstacleGrid;
    
    int v;
    while(scanf("%d",&v)){
        //数组输入结束
        if(v==-2){
            break;
        }
        //每行输入结束
        if(v==-1){
            obstacleGrid.push_back(vec);
            vec.clear();//每次vec数组要进行清空操作
        }else{
            vec.push_back(v);
            //vector<int> vec(vec.size(),0);
        }
        
    }
    
    for(int i=0;i<obstacleGrid.size();i++){
        for(int j=0;j<obstacleGrid[0].size();j++){
            cout<<obstacleGrid[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"------------------------"<<endl; 
    Solution solution;
    int r=solution.uniquePathsWithObstacles(obstacleGrid);
    cout<<r<<endl;
}

补充：二维vector的输入

先将元素加入一维数组，每行结束后加入二维数组，最后要对一维数组进行清空（clear()）！！！！

while(scanf("%d",&v)){
        if(v==-2){
            break;
        }
        if(v==-1){
            obstacleGrid.push_back(vec);
            vec.clear();//每次vec数组要进行清空操作
        }else{
            vec.push_back(v);
            //vector<int> vec(vec.size(),0);
        }
        
    }