Leetcode 62 不同路径

2023-12-29 18:32:07

题意理解:

????????一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )

????????

? ? ? ? 要求:机器人只能向右走或向下走

? ? ? ? 目标:从起始位置走到终止位置有多少种路径

解题思路

? ? ? ? 我们采用动态规划的思路来求解。

? ? ? ? 1.定义dp[i][j]表示从起始位置到(i,j)有多少种走法。

? ? ? ? 2.进入每个格子有两种方式,

????????????????第一种是从上面的格子走下来。

? ? ? ? ? ? ? ? 第二种是从左面的格子走到右边进入。

? ? ? ? ? ? ? ? 则可以得到递推公式:dp[i][j]=dp[i-1][j]+dp[i][j-1]

? ? ? ? 3.初始化:根据题意,有dp[i][0]=1,一直往下走;dp[j][0]一直往右走

? ? ? ? 4.遍历顺序,由于机器人只能往下|往右走,故遍历顺序:左->右,上->下

? ? ? ? 5.打印dp数组用于验证和debug

1.动态规划解题

  public int uniquePaths(int m, int n) {
        //定义存储
        int[][] dp=new int[m][n];
        //初始化
        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];
    }

2.分析

时间复杂度:O(m×n) 时间复杂度主要耗费在双for循环

空间复杂度:O(m×n) 主要空间耗费在动态数组dp上

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135277533
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。