不同路径。

不同路径。,第1张

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


机器人每次只能向下或者向右移动一步。


机器人试图达到网格的右下角(在下图中标记为 “Finish” )。


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

题解: 机器人走过的路径可以抽象为一棵二叉树,而叶子节点就是终点。


按照动态规划来写,

  1. 确定dp数组dp[i][j](dp table)以及下标的含义
  2. 确定递推公式,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  3. dp数组的初始化,dp[i][0]一定都是1
  4. 确定遍历顺序
  5. 推导结果

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

参考:公众号 代码随想录 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562305.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-01
下一篇 2022-04-01

发表评论

登录后才能评论

评论列表(0条)

保存