LeetCode-Unique Paths

题目要求：

• 二维矩阵，从左上角到右下角共有多少条路
• 只能向前或向下

解法：

• 回溯（超时，不能AC）
• Dp： f[i][j] = f[i-1][j] + f[i][j-1]

源码如下：

class Solution {
public:
    /*
    * 1. 回溯解法
    * 2. 非递归解法
    */
    
    //非递归解法
    void non_uniqpath(int m,int n,int& num){
        
        vector<vector<int>> flag;
        flag.resize(m);
        for_each(flag.begin(),flag.end(),[n](vector<int>& pa){pa.resize(n,0);});
        for (int i=0;i<n;i++){
            flag[0][i] = 1;
        }
        for (int i=0;i<m;i++){
            flag[i][0] = 1;
        }
        for (int i=1;i<m;i++){
            for (int j=1;j<n;++j){
                flag[i][j] = flag[i-1][j]+flag[i][j-1];
            }
        }
        num = flag[m-1][n-1];
    }
    
    
    
    //递归解法
    void rec_uniqpath(int m,int n,int row,int col,int& num){
        if (row==m-1 && col==n-1){
            num++;
            return;
        }
        if (col < n-1)
        rec_uniqpath(m,n,row,col+1,num);
        if (row < m-1)
        rec_uniqpath(m,n,row+1,col,num);
    }
    
    int uniquePaths(int m, int n) {
        int num{0};
        //rec_uniqpath(m,n,0,0,num);
        non_uniqpath(m,n,num);
        return num;
    }
};