讨论/《中级算法》 - 不同路径/
《中级算法》 - 不同路径
共 8 个回复

脑子比较笨,没办法一下子get 到题意里隐含的巧妙关系,所以根据经验,先做出假设:设dp[i][j]为 i * j 网格中Robot 从左上角到右下角的总路径数量。

然后将待求解问题分解成小问题,例如针对m = 3 & n = 3,那么最小的问题就是1 * 1 网格,然后1 * 2,1 * 3,2 * 1,2 * 2 等等,将所有规模罗列出来,人脑求解,大致演算过程如下:

dp[0][0] = 1
dp[0][1] = 1
dp[0][2] = 1
dp[1][0] = 1
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[1][1] + dp[0][2] = 2 + 1 = 3
dp[2][0] = 1
dp[2][1] = dp[2][0] + dp[1][1] = 1 + 2 = 3
dp[2][2] = dp[2][1] + dp[1][2] = 3 + 3 = 6

然后我们发现当前项其实就是它的 上 & 左 两项的和!Bingo,递推公式(状态转移方程)就出来了:

dp[i][j] = (j > 0 ? dp[i][j - 1] : 0) + (i > 0 ? dp[i - 1][j] : 0);

所以我个人理解的动态规划解题的过程,其实就是先手动演算一下枚举出所有子问题的解,然后找前后几项之间的规律,然后递归公式就总结出来了,最后思考下边界条件(这道题边界条件就是当i - 1 < 0 时怎么处理),然后根据公式去理解,原来从原点到位置(i,j)的路径数量就是位置(i-1, j)(i, j-1)的路径数量之和!

TS 实现

function uniquePaths(m: number, n: number): number {
    const dp = [[1]];
    for (let i = 0; i < m; i++) {
        if (i > 0) {
            dp.push([]);
        }
        for (let j = 0; j < n; j++) {
            // console.log(i, j);
            if (i === 0 && j === 0) {
                continue;
            }
            dp[i][j] = (j > 0 ? dp[i][j - 1] : 0) + (i > 0 ? dp[i - 1][j] : 0);
        }
    }
    return dp[m - 1][n - 1];
};

总结:作出假设 > 枚举所有子问题的解 > 找规律 > 提炼并完善递推公式(即状态转移方程)> 根据递推公式理解题意

3

执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗:5.9 MB, 在所有 C++ 提交中击败了74.93% 的用户

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

    }
};
1
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(i == 0 && j == 0){
                    dp[0][0] = 1; // 到达最开始的位置就是一个路
                    continue;
                }
                if(i-1<0){
                    dp[i][j] = dp[i][j-1];
                }else if(j-1<0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
1

dfs爆搜(m*n>260会超时)

class Solution {
public:
    int uniquePaths(int m, int n) {
        dfs(m,n,1,1);
        return res;
    }
private:
int res = 0;
int dx[2] = {0,1};
int dy[2] = {1,0};
//dfs爆搜
    void dfs(int m,int n,int x,int y){
        if(x==m&&y==n){
            res++;
            return;
        }
        for(int i=0;i<2;i++){
            int newX = x+dx[i];
            int newY = y+dy[i];
            if(newX<=m&&newY<=n)
                dfs(m,n,newX,newY);
        }
    }
};


动态规划

在这里插入图片描述

dp关系的确定步骤:

  1. 找到选择
  2. 找出base case
  3. 确定更新的方向

具体实施:
2. 看最后的终点,只能由上左两个位置得到,即dp[i][j] = dp[i-1][j]+dp[i][j-1];
3. base case:dp[1][j]=dp[i][1]=1第一行和第一列均为一种路径
4. 这样就可以确定dp数组的更新方向了--从左往右或者从上往下(只要能保证dp[i][j]更新前,上和左两个方向已经被更新)

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[100][100];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<m;i++)
            dp[i][0] = 1;
        for(int i=0;i<n;i++)
            dp[0][i] = 1;
        //更新dp数组
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

};

动态规划典型环节:
1、初始化:从(0,0)到首行、首列中的任意位置路径只有1条
2、状态转移条件:新的一行,或新的一列
3、状态转移表达式:pathNum(i, j) = pathNum(i - 1, j) + pathNum(i, j - 1)
4、退出条件:从节点(0,0)遍历到节点(m - 1, n - 1),pathNum(m - 1, n - 1)中即为最终解

int uniquePaths(int m, int n){
    if (m == 1 || n == 1) {
        return 1; 
    }
    int i;
    int j;

    int roads[n];
    for (j = 0; j < n; j++) {
        roads[j] = 1;
    }

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            roads[j] = roads[j - 1] + roads[j]; // 当前路径数 = 左边的路径数 + 上一行的路径数
        }
    }
    return roads[n - 1];
}

  • f(x, y) = f(x - 1, y) + f(x, y - 1);
  • f(1, y) = 1;
  • f(x, 1) = 1;
var uniquePaths = function (m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(1));
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};

啥也不会,只知道找规律
每个格子的数表示到达这个格子有几种路径。首先第一行和第一列都是1.然后发现其他的都是 上格子的数 + 左格子的数。最后一个格子就是答案了。emmmmm。做完了也不知道做了个啥。

public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        for(int i = 0;i < m; i++){
            arr[i][0] =1;
        }
        for(int i = 0;i < n; i++){
            arr[0][i] = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1;j < n;j++){
                arr[i][j] = arr[i-1][j] + arr[i][j-1];
            }
        }
        return arr[m-1][n-1];
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:35.5 MB, 在所有 Java 提交中击败了15.50%的用户

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