leetcode 62 不同路径

「爱情、让人受尽委屈。」 2022-08-28 05:52 127阅读 0赞

## 前言 ##

题目：[62. 不同路径][62.]

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

--------------------

## 提交代码 ##

一维的动态规划，类似于[leetocde 70 爬楼梯][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];
        }
    };

[62.]: https://leetcode-cn.com/problems/unique-paths/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.md
[leetocde 70]: https://blog.csdn.net/sinat_38816924/article/details/120795702