不同路径-DP算法求解

[liuyingbin19222]

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？

输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

• 找到一条路;

  /**
  * @param {number} m
  * @param {number} n
  * @return {number}
  */
  var startx = 0;
  var starty = 0;
  var result = [];
  var uniquePaths = function(m, n) {
  while(1){
      if(startx + 1 < m ) {
          ++startx;
          result.push({"startx:":startx})
      } 
      if(starty + 1 < n){  
          ++starty;
          result.push({"starty:":starty});
      }
      if(startx == m-1 && starty == n-1){
          break;
      }
  }
  return result;
  };

[liuyingbin19222]

• 使用DP算法找到所有的路径:

  class Solution {
  public:
  int uniquePaths(int m, int n) {
      int **dp = (int **)malloc(sizeof(int *) * n);
      for(int i = 0; i < n;i++){  
          dp[i] = (int *)malloc(sizeof(int *) * m);
      }
  
      for(int i = 0;i < n; i++){
          for(int j = 0;j < m; j++){
              if(i== 0 || j == 0){
                  dp[i][j] = 1;
              }else {
                  dp[i][j] = dp[i-1][j] + dp[i][j-1];
              }
          }
      }
      return dp[n-1][m-1];
  }
  };

[liuyingbin19222]

考虑障碍物: 输入: [   [0,0,0],   [0,1,0],   [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0){
            return 0;
        }
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        vector<vector<long>> v(m,vector<long>(n));
        v[0][0] =! obstacleGrid[0][0];
        for(int i = 1; i < m ;i++) v[i][0] = (obstacleGrid[i][0] || v[i-1][0] == 0)? 0 : 1;
        for(int j = 1; j < n; j++) v[0][j] = (obstacleGrid[0][j] || v[0][j-1] == 0)? 0 : 1;
        for(int i = 1; i < m; i++){
            for(int j = 1;j < n;j++){
                v[i][j] = obstacleGrid[i][j] ? 0 : v[i-1][j] + v[i][j-1];
            }
        }
        return v[m-1][n-1];
    }
};