[数据结构与算法]leetcode 62 不同路径

前言

题目：62. 不同路径

参考题解：不同路径-代码随想录

提交代码

一维的动态规划，类似于leetocde 70 爬楼梯,比较简单。二维的动态规划，比如这一题，也不难。

我最开始看错题目，以为找最短到达路径。代码如下。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> maze(m,vector<int>(n,0));
        
        // 对上边界和左边界初始化
        maze[0][0] = 0;
        for(int i=1; i<n; i++)
            maze[0][i] = maze[0][i-1] + 1;
        for(int i=1; i<m; i++)
            maze[i][0] = maze[i-1][0] + 1;

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                maze[i][j] = min(maze[i-1][j],maze[i][j-1]) + 1;
            }
        }

        return maze[m-1][n-1];
    }
};

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

代码稍微改下就成。递推公式为：maze[i][j] = maze[i-1][j]+maze[i][j-1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> maze(m,vector<int>(n,0));
        
        // 对上边界和左边界初始化
        maze[0][0] = 1;
        for(int i=1; i<n; i++)
            maze[0][i] = 1;
        for(int i=1; i<m; i++)
            maze[i][0] = 1;

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                maze[i][j] = maze[i-1][j]+maze[i][j-1];
            }
        }

        // for(int i=0; i<m; i++){
        //     for(int j=0; j<n; j++){
        //         cout<<maze[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }

        return maze[m-1][n-1];
    }
};