NC34 题解 | #求路径#

题目意思

• 给你一个二维矩阵，需要找出从左上角走到右下角的不同的方案数。每次只能向下或者向右移动。过程中只要有一步不一样这种走法就不一样。

  思路分析

• 题目意思很简单，其实这是一个排列组合的经典的题目。只要用到高中知识。我们发现，每种方案走的步数其实是固定的。对于一个m行n列的矩阵，我们走的步数其实就是固定了走n+m-2步，其中，我们要选择n-1步向右边走，m-1步向下走。这就是一个很经典的排列组合问题，在n+m-2中选择n-1步向右走，剩下的自然就是向下走了。最终的答案就是,等价于，下面，我们就来介绍求组合数的三种方法。

解法一 循环相乘

• 我们通过推导可以得到如下的式子。

题目说了答案的范围一定在int范围内，所以我们可以直接循环得到，但是要注意的是阶乘可能很大，记得使用unsigned long long 防止爆long long。当然，这种做法还是比较局限的。

• 代码如下
  • 循环一遍，时间复杂度为O(n)
  • 只用了几个变量存储，空间复杂度为O(1)

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    typedef unsigned long long ll;
    int uniquePaths(int m, int n) {
        // write code here
        ll ans=1;
        // 转化为组合数进行求解
        ll a=n+m-2,b=max(n-1,m-1);
        if(b==0||b==a) return 1;  // 特殊情况直接返回
        // 按照推导的公式枚举，注意范围
        for(ll i=a;i>b;i--){
            ans=ans*i;
        }
        for(ll i=1;i<=(a-b);i++){
            ans/=i;
        }

        return ans;
    }
};

解法二 递归写法

• 学过数学的同学基本都知道，排列组合和杨辉三角的关系十分密切，我们可以通过杨辉三角得到一些组合数。
  
  如上面的图，我们发现右边就是一个杨辉三角，杨辉三角的性质大家应该都知道吧，出了两端的数字为1，其他的就是当前位置的数为上面两边的数的和。如果右边那个图不是很清楚，那就看一下左边的图，也就是这个位置的数为上面的位置的数加上上面位置左边的数。转化为一个DP方程就是.这个公式学过排列组合的同学应该都知道吧。

• 代码如下
  • 需要进行递归处理，时间复杂度为O(n*m)
  • 每层递归的空间复杂度为O(1),最坏的情况是递归n层，所以空间复杂度为O(n)

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    // 计算C(a,b)
    int C(int a,int b){
        // b大于a的情况不存在，所以返回0
        if(b>a) return 0;
        if(b==0||b==a) return 1;  // 如果b=0,或者b=a，那么只有一种选法
        return C(a-1,b)+C(a-1,b-1); // 否则进行递归
    }
    int uniquePaths(int m, int n) {
        // write code here
        return C(n+m-2,n-1);
    }
};

解法三 非递归DP写法

• 这种写法和第二种的思路是一样的，但是这里采用的是非递归的写法。需要我们存储之前计算过的每一种状态，当前的状态由之前的状态转移过来。

• 代码如下

  • 双重循环遍历，时间复杂度为O(nm)
  • 开了一个二维数组存储中间的每一个状态，空间复杂度为O(nm)

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    // 定义状态方程，表示在杨辉三角里面的第i行第j个位置
    int dp[220][220];
    int uniquePaths(int m, int n) {
        // write code here
        for(int i=0;i<=205;i++){
            for(int j=0;j<=i;j++){
                // 状态转移，当C(i,0)或者C(i,i)很显然就是1
                if(j==0||j==i) dp[i][j]=1;
               // 否则进行状态的转移,转移方程就是下面的公式
                else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            }
        }
        return dp[n+m-2][n-1];
    }
};