题目

给定一个m行n列的网格, 计算出从左上角移动到右下角的路径数量, 只能向左或向下移动.

Input: m = 3, n = 2
Output: 3
Input: m = 7, n = 3
Output: 28

思路1

未知数量问题首先考虑递归. 但是递归时间复杂度太高.

void pathRecrution(int m, int n, int &count) {
    if (m == 0 || n == 0) {
        count++;
        return;
    } else {
        pathRecrution(m-1, n, count);
        pathRecrution(m, n-1, count);
    } 
}

int uniquePaths(int m, int n) {
    int count = 0;
    pathRecrution(m-1,n-1,count);
    return count;        
}

思路2

采用数组叠加的方式, 就是将递归转化为循环.

int uniquePaths(int m, int n) {
  vector<vector<int>> vec(m,vector<int>(n,0));
  vec[0][0] = 1;

  for (size_t i = 0; i < m; i++)
  {
      for (size_t j = 0; j < n; j++)
      {
          if (i < m - 1) vec[i+1][j] += vec[i][j];
          if (j < n - 1) vec[i][j+1] += vec[i][j];
      }
  }
  return vec[m-1][n-1];        
}

总结

巧妙使用高维数组, 通过对二维数组进行累加实现计数.