leecode第六十二题(不同路径)

时间:2022-12-10 13:03:49

leecode第六十二题(不同路径)

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==1||n==1)
            return 1;
        
        vector<vector<int>> path;//建立一个二维数组
        for(int i=0;i<m;i++)
        {
            vector<int> zeros;
            for(int j=0;j<n;j++)
                zeros.push_back(0);
            path.push_back(zeros);
        }
        
        for(int i=m-1;i>=0;i--)//从右下角到左上角遍历
        {
            for(int j=n-1;j>=0;j--)
            {
                if(i==m-1 || j==n-1)//在边界处值必须为1
                {
                    path[i][j]=1;
                    continue;
                }
                path[i][j]=path[i+1][j]+path[i][j+1];//动态规划,当前节点可能的路径等于下面和右面的节点路径可能之和
            }
        }
        
        return path[0][0];
    }
};

分析:

这题比较有意思,一开始想到动态规划,然后用递归写了不到六行的代码,但是提示我时间超时了。后来一想递归的确太占内存和时间了,为了解决这个问题,我想到用循环,但一开始没想到辅助空间实现动态规划,还是只想着从开头遍历,想了一会才觉得用辅助空间,然后就是画图,找找规律,然后发现从目的地回溯真的很好用,下次再用动态规划时候该想想这个思路。