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];
    }
相关文章
|
数据采集 编解码 运维
PMU
PMU
1893 1
|
算法 Java API
生产升级JDK 17 必读手册
DK 17 在 2021 年 9 月 14 号正式发布了!根据发布的规划,这次发布的 JDK 17 是一个长期维护的版本(LTS)。
1684 0
|
存储 Java 定位技术
gis利器之Gdal(二)shp数据读取
本文首先简单介绍了空间数据shp数据的基本知识,其常见的文件组成形式。使用qgis软件对数据进行常规预览,最后重点介绍了使用gdal对矢量信息进行读取,​包括空间信息和属性信息
2038 0
gis利器之Gdal(二)shp数据读取
|
1月前
|
人工智能 自然语言处理 安全
从单点工具到任务闭环——海信AI原生开发实践
9月22日云栖大会,海信曲栋分享《从单点工具到任务闭环》:历经Copilot、通义灵码到Qoder三阶段选型,构建Prompt→Harness→Loop→Graph四层叠加式AI原生开发范式;需求对齐缩至1天,端到端交付提效3–5倍,老系统亦提升1.3–2倍。
322 3
|
1月前
|
存储 人工智能 开发者
2026 年阿里云 GPU 云服务器收费价格多少钱?最新版收费清单全解析
2026年阿里云GPU云服务器的收费体系灵活,从小时级临时算力到年度长期算力,覆盖AI训练、推理、渲染等多样化需求。整体成本由实例规格、付费模式、地域、存储带宽等多个因素共同决定,新用户大促期间可以拿到非常可观的折扣。在选型前,建议先用CLI查询实例规格,结合业务运行时长、算力需求,做完整的成本测算,合理选择计费方案,同时做好资源释放、快照管理,规避不必要的额外支出。企业在规划大模型项目算力预算时,优先评估业务持续运行时间,按需选择T4、A10、L20等不同显卡实例,搭配节省计划或者包年包月优惠,最大化控制算力成本,保障AI业务稳定落地。
550 0
|
3月前
|
人工智能 数据可视化 测试技术
面试预约电话如何自动化?|阿里云智能联络中心实操指南
阿里云智能联络中心语音智能体,助力招聘高效邀约:AI自动外呼确认候选人意向与时间,支持自然对话、实时打断,准确率95%,1.8秒低延迟,最快1天上线。
339 1
|
11月前
|
存储 弹性计算 网络安全
阿里云用户上云流程参考:从账号注册、实名认证到领取和使用优惠券流程指南
不管我们是需要在阿里云平台注册域名还是需要购买云服务器及其他云产品,第一步都首要完成账号注册与实名认证流程,此为后选购各类云产品的必要前提。同时,在购买过程中,部分云服务器及其他云产品支持叠加使用阿里云赠送的各种优惠券,有效降低采购成本。本文将以图文的形式,为大家解析从阿里云账号注册、实名认证以及优惠券领取与使用的完整流程,助力用户以更优价格选购心仪的云产品。
932 11
|
4月前
|
机器学习/深度学习 缓存 人工智能
Kimi K3 登陆阿里云百炼:2.8万亿参数旗舰模型,输入仅20元/百万Token
全球首个开源3万亿级大模型Kimi K3(2.8万亿参数)正式上线阿里云百炼平台,支持100万Token超长上下文、原生视觉理解与深度推理。具备文本生成、多模态分析及复杂逻辑能力,输入20元/百万Token(缓存命中仅2元),定位高端AI开发场景。在阿里云百炼官网:https://t.aliyun.com/U/fPVHqY 免费领取千万Tokens
|
6月前
|
弹性计算 监控 网络协议
服务器部署后用户反馈访问慢,一份 SRE 视角的全链路网络诊断实战清单
本文总结后端/运维/站长高频遇到的“用户访问异常”问题,提出可落地的“全链路诊断七步法”:从多地Ping、TCPing、HTTP分段测速、Traceroute定位拥塞点,到DNS一致性检查与IP信誉扫描。不讲理论,只教命令、工具和典型现象判断,助你快速定位网络瓶颈,告别“本地正常、用户炸锅”的排查困境。
884 0
|
人工智能 运维 安全
在线客服机器人持续运营保障体系测评:从技术架构到服务支持,这些厂商值得推荐!
本文聚焦智能客服机器人选型新趋势,从技术架构、数据安全、运维迭代和服务交付四大维度,深度评估合力亿捷、Zendesk、瓴羊Quick Service等主流厂商的持续运营保障能力,助力企业摆脱“僵尸应用”困境,构建长期稳定高效的智能客服体系。