【奇技淫巧】– 走地图的不同路径

题目:不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

思路

这题其实就是爬楼梯问题的二维抽象罢了,很简单。又一次证明递归会超时。

把图画出来会发现就是个杨辉三角,问题就在于:你是要开数组,还是不开数组?要是开数组,开多大?

解法1:二维数组

用杨辉三角的办法,开一个二维数组,把每个空都填上。

代码1:

int uniquePaths(int m, int n) {
        // DP with 2 dimensions array
        int a[m][n];
        for (int i = 0; i < m; i++) {
            a[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            a[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                a[i][j] = a[i-1][j] + a[i][j-1];
            }
        }
        return a[m-1][n-1];
    }

解法2:一维数组(M+N)

把地图想象成一个正方形的地图,如果我们需要求坐标(m,n)处的值,其实前面那些只是铺垫,并没有留下的必要。
比方说我们现在要(4,5)的值,那么我们最终只需要从反斜线(0,8)->(8,0)这条线上找到(4,5),所以我们以斜线的方式前进,每次刷新的时候,就当数组的原住民不存在了,它们只需要提供一个数值。

语言是无力的,看代码

代码2:

int uniquePaths(int m, int n) {
    int k = m + n - 1;
    vector<int> a(k, 0);
    if (k == 1)
        return 1;

    a[0] = 1;
    a[1] = 1;

    int count = 2;
    while (k > 2) {
        for (int i =count-1; i >0; i--) {
            a[i] = a[i] + a[i - 1];
            a[count] = 1;
        }
        count++;
        k--;
    }
    
    return a[n-1];
}

解法3:一维数组(M+N)/2

很快你会发现,原先的斜线数组,其实是中心对称的。你懂得。

我饿了,吃饭去了。

本文地址:https://blog.csdn.net/qq_43762191/article/details/107619305

(0)
上一篇 2022年3月22日
下一篇 2022年3月22日

相关推荐