Unique Paths

• 问题介绍
  • 问题描述：A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).How many possible unique paths are there?
  • 
  • • 示例：
    • Input: m = 3, n = 2
    • Output: 3
    • Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down;2. Right -> Down -> Right;3. Down -> Right -> Right
  • 约束条件：m and n will be at most 100.
• 解决思路
  • 思路一：
    • 拿到题目首先想到的方法是回溯法用递归解决问题，即每次在当前位置向右走一步，然后判断之后的位置是否处于终点位置，如果是则计数器加1，否则的话判断走后的位置是否超过边界，如果超过的话直接返回；从向右走一步的递归中返回后，进行向下走一步的操作，同样对走后的位置进行三个判断：是否处于终点？是否超过边界？再走下一步？最终递归全部返回后，便能得到所有到达终点的唯一路径数；
    • 问题：时间复杂度过高，相同的子问题进行了太多次的重复计算；
  • 思路二：
    • 采用动态规划法，将原问题分解为子问题，而子问题之间是存在相互依赖关系的，用数组记录计算过的子问题，从而减少重复计算，达到符合条件的时间复杂度O(mxn);具体做法：对于任何位置[i][j]到达他的不相同的路径数目记录为count[i][j],那么可以得到count[i][j]=count[i-1][j]+count[i][j-1];所以在动态规划算法中，初始化一个m+1xn+1的矩阵，将第一行、第一列的元素均赋值为0，之后将count[1][1]赋值为1就可以利用上述规则计算所有的位置对应的值了，而最后问题需要求解的值即为count[m][n];
• 代码
  • 回溯法递归算法：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int count=0;
        proc(1,1,m,n,count);
        return count;
    }
    
    void proc(int p_m,int p_n,int m,int n,int& count)
    {
        if(p_m>m||p_n>n)
        {
            return;
        }
        else if(p_m==m&&p_n==n)
        {
            count++;
            return;
        }
        else
        {
            proc(p_m+1,p_n,m,n,count);
            proc(p_m,p_n+1,m,n,count);
        }
    }
};

• 动态规划算法：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int** resp=new int*[m+1];
        for(int i=0;i<m+1;i++)
        {
            resp[i]=new int[n+1];
            resp[i][0]=0;
        }
        for(int i=0;i<n+1;i++)
        {
            resp[0][i]=0;
        }
        
        for(int i=1;i<m+1;i++)
        {
            for(int j=1;j<n+1;j++)
            {
                if(i==1&&j==1)
                {
                    resp[i][j]=1;
                }
                else
                {
                     resp[i][j]=resp[i-1][j]+resp[i][j-1];                   
                }

            }
        }
        return resp[m][n];
    }
};