当前位置：首页 > article >正文

LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

article 2024/11/17 21:53:31

文章目录

前言
LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】
- 题目描述与分类
- 思路
- - 思路1：动态规划
  - 思路2：递归实现
  - 简洁写法补充：2024.1.30
资料获取

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

题目描述与分类

牛客：不同路径的数目(一)

leetcode：LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

题目内容：一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

思考区

分类：动态规划/线性DP（二维）

约束条件：

1、机器人每次只能往右或者往下走。

2、机器人不能越界。

思路

思路1：动态规划

定义状态方程：

dp[i][j] = val  i表示行，j表示列，val表示方案数量
当i>1 && j>1  dp[i][j] = dp[i][j-1] + dp[i-1][j]
当i=0时，dp[i][j] = dp[i][j-1]
当j=0时，dp[i][j] = dp[i-1][j]

复杂度分析：

时间复杂度：O(n*m)
空间复杂度：O(n*m)

代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
       //定义dp数组
        int[][] dp= new int[m][n];
        
        for (int i = 0;i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

class Solution {

    //线性dp
    //dp(i, j) = dp(i-1,j) + dp(i,j-1)
    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[i][j] = 1;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

思路2：递归实现

import java.util.*;


public class Solution {
    
    
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        if (m == 1 || n == 1) {
            return 1; 
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

上面的时间复杂度是2ⁿ，如何优化呢？进行记忆化状态方程

class Solution {
    private int[][] dp;

    public int uniquePaths(int m, int n) {
        if (dp == null) {
            dp = new int[m + 1][n + 1];
        }
        if (m == 1 || n == 1) {
            return 1;
        }
        if (dp[m][n] == 0) {
            dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
        }
        return dp[m][n];
    }
}

简洁写法补充：2024.1.30

class Solution {

    int[][] dp = new int[101][101];

    //线性dp
    //dp(i, j) = dp(i-1,j) + dp(i,j-1)
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) 
            dp[m][n] = 1;
        if (dp[m][n] != 0) return dp[m][n];
        dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
        return dp[m][n];
    }
}