04_不同路径

简介: 04_不同路径

62.不同路径

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

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

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

  • 输入:m = 3, n = 7
  • 输出:28

示例 2:

  • 输入:m = 2, n = 3
  • 输出:3

解释: 从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 3:

  • 输入:m = 7, n = 3
  • 输出:28

示例 4:

  • 输入:m = 3, n = 3
  • 输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10^9

动态规划

机器人从(0,0)位置出发,到(m-1, n-1)终点。

按照动规五部曲来分析:

1、确定dp数组(dp table)以及小标的含义

dp[i][j]:表示从(0, 0)出发,到(i,j)有dp[i][j]条不同的路径。

2、确定递推公式

要想求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。

此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

3、dp数组的初始化

如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

所以初始化代码为:

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

4、确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

5、举例推导dp数组

代码如下:

/**
     * 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类
     * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
     * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
     * 4. 遍历顺序 一行一行遍历
     * 5. 推导结果 。。。。。。。。
     *
     * @param m
     * @param n
     * @return
     */
    public static 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 i = 0; i < n; i++) {
            dp[0][i] = 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];
    }
//状态压缩
 /**
     * 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类
     * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
     * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
     * 4. 遍历顺序 一行一行遍历
     * 5. 推导结果 。。。。。。。。
     *
     * @param m
     * @param n
     * @return
     */
    public static 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 i = 0; i < n; i++) {
            dp[0][i] = 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];
    }
相关文章
|
数据安全/隐私保护 智能硬件
智能家居系统入门指南
随着科技的飞速发展,智能家居系统已不再是遥不可及的梦想。本文将带你走进智能生活的世界,从基础概念到实用设备,再到搭建步骤和常见问题解答,全方位解析如何打造一个舒适、便捷、高效的智能居家环境。让我们一起探索,如何通过简单的操作,实现家居生活的智能化升级。
|
前端开发
CSS优先级:如何解决样式冲突?
CSS优先级:如何解决样式冲突?
|
前端开发
CSS实现心形
CSS实现心形
85 0
|
Web App开发 PHP 开发者
深入理解PHP中的命名空间
【5月更文挑战第1天】在PHP的编程实践中,命名空间是管理代码中类名、函数名和常量名的一个强大工具,它能够解决名称冲突的问题,并使代码更加模块化。本文将深入探讨PHP命名空间的概念、语法以及它们如何帮助我们构建更加清晰和可维护的代码结构。通过实例分析,我们将了解如何合理地使用命名空间来优化项目架构,并讨论其与自动加载机制的结合使用,以提升代码的重用性和灵活性。
|
前端开发 容器
react map使用方法详解
react map使用方法详解
1012 0
|
存储 C语言
【C语言】学生管理系统
【C语言】学生管理系统
298 0
|
SQL 设计模式 缓存
Java并发编程基础盘点2-单例模式
Java并发编程基础盘点2-单例模式
178 0
|
传感器 机器人 atlas
会后空翻的机器人、会开门的机器狗:揭秘波士顿动力Atlas&Spot
IEEE Spectrum获准进入波士顿动力总部,用高速摄像机和强闪光灯拍摄波士顿动力机器人的动作——跑步、攀爬、跳跃等等,将其敏捷性定格在这组珍贵的超高清照片中。
会后空翻的机器人、会开门的机器狗:揭秘波士顿动力Atlas&Spot
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!