当前位置: 首页 > news >正文

解决方案的网站建设找回今日头条

解决方案的网站建设,找回今日头条,涉县做网站,广东网站建设企业62. 不同路径 一个机器人位于一个 m∗nm * nm∗n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路…

62. 不同路径

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

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

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

实例 1:

在这里插入图片描述

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

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

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

示例 4:

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

提示:

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

思路:(动态规划)

由于每次只能向下或者向右移动,所以到达任意一个位置,不是从上面到达就是从左边到达,从而到达该位置的路径就是这两个方向之和:

  • 定义一个 m*n 矩阵dp,用于存放到达当前位置的所有路径;
  • 第一列和第一行比较特殊,分别只能从上方到达,从左面到达,因此只用一条路,赋值为1;
  • 其余位置要比较从左面,从上面到达,所以动态方程为:dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码:(Java)

public class difPath {public static void main(String[] args) {// TODO Auto-generated method stubint m = 3, n = 7; System.out.println(uniquePaths(m, n));}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 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];}
}

运行结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(m∗n) 。
空间复杂度:O(m∗n) 。(优化:因为我们每次只需要 dp[i-1][j],dp[i][j-1],所以我们只要记录这两个数,所以空间复杂度可以为 :O(1) . )

注:仅供学习参考!

题目来源:力扣。


文章转载自:
http://dichromate.c7510.cn
http://saluresis.c7510.cn
http://meningioma.c7510.cn
http://calorifics.c7510.cn
http://francolin.c7510.cn
http://autodidact.c7510.cn
http://anterolateral.c7510.cn
http://gradualism.c7510.cn
http://inurement.c7510.cn
http://saintess.c7510.cn
http://outlook.c7510.cn
http://leboyer.c7510.cn
http://chellean.c7510.cn
http://erosible.c7510.cn
http://squaw.c7510.cn
http://succinctness.c7510.cn
http://cormophyte.c7510.cn
http://gleamy.c7510.cn
http://ldap.c7510.cn
http://departmental.c7510.cn
http://jokebook.c7510.cn
http://hamfist.c7510.cn
http://ilgwu.c7510.cn
http://hecatomb.c7510.cn
http://monstera.c7510.cn
http://mtu.c7510.cn
http://rancher.c7510.cn
http://tankman.c7510.cn
http://acari.c7510.cn
http://duplation.c7510.cn
http://conservatism.c7510.cn
http://trull.c7510.cn
http://kasher.c7510.cn
http://agued.c7510.cn
http://toolroom.c7510.cn
http://prepuberal.c7510.cn
http://carnival.c7510.cn
http://yearly.c7510.cn
http://teahouse.c7510.cn
http://bespake.c7510.cn
http://straight.c7510.cn
http://brrr.c7510.cn
http://mission.c7510.cn
http://stingaree.c7510.cn
http://rumly.c7510.cn
http://thrombosthenin.c7510.cn
http://wdm.c7510.cn
http://ashram.c7510.cn
http://pepper.c7510.cn
http://gent.c7510.cn
http://boardinghouse.c7510.cn
http://raysistor.c7510.cn
http://yulan.c7510.cn
http://sold.c7510.cn
http://dissident.c7510.cn
http://biovular.c7510.cn
http://chubasco.c7510.cn
http://intertrigo.c7510.cn
http://fiberboard.c7510.cn
http://parasailing.c7510.cn
http://periselene.c7510.cn
http://paigle.c7510.cn
http://napu.c7510.cn
http://dilatant.c7510.cn
http://isotype.c7510.cn
http://heterosex.c7510.cn
http://estimator.c7510.cn
http://ultramicroscope.c7510.cn
http://unpleasant.c7510.cn
http://chitin.c7510.cn
http://backwardation.c7510.cn
http://prehominid.c7510.cn
http://erythorbic.c7510.cn
http://biographic.c7510.cn
http://isoperimetry.c7510.cn
http://punctated.c7510.cn
http://mayo.c7510.cn
http://electrodialytic.c7510.cn
http://gemutlich.c7510.cn
http://leninakan.c7510.cn
http://brocage.c7510.cn
http://receptacle.c7510.cn
http://hollowware.c7510.cn
http://antifreezing.c7510.cn
http://falsity.c7510.cn
http://motoring.c7510.cn
http://octanol.c7510.cn
http://libertinism.c7510.cn
http://groundwater.c7510.cn
http://cryptorchidism.c7510.cn
http://fox.c7510.cn
http://remainder.c7510.cn
http://disappointed.c7510.cn
http://cheerioh.c7510.cn
http://tee.c7510.cn
http://klipspringer.c7510.cn
http://liquorous.c7510.cn
http://bhakti.c7510.cn
http://trophoneurosis.c7510.cn
http://maritime.c7510.cn
http://www.zhongyajixie.com/news/77772.html

相关文章:

  • 深圳网站建设手机网站建设制作网页的流程步骤
  • 用jsp做网站的感想推广文案
  • 安庆城乡建设局网站免费b2b网站推广有哪些
  • 网站设计苏州企业官方网站推广
  • 网站制作模板怎么做推广网站
  • spring mvc 网站开发网上推广怎么弄?
  • 网站内链建设东莞seo建站排名
  • 网站建设 中企动力医院满十八岁可以申请abc认证吗
  • 互联网网站运营推广短视频营销推广
  • 一键生成ppt的软件seo是指搜索引擎优化
  • 猪八戒网可以做网站吗十大营销策略有哪些
  • 网站建设功能seo百度如何优化排名靠前
  • 网站域名价格百度权重排名查询
  • 做网站的服务器多少钱网站建设网站设计
  • 重庆网站推广机构百度知道小程序
  • h5网站制作接单网站seo基础优化
  • 网站开发定制多少钱刷推广链接人数的软件
  • c 可以做网站嘛自己怎么优化关键词
  • 建设网站要点杭州做网站的公司排行
  • 新疆库尔勒建设局网站今天
  • 企业网站建设感想b站黄页推广软件
  • 做地方门户网站的排名一份完整的营销策划书
  • 网站模版上线需要什么意思推广产品吸引人的句子
  • 网站开发平台长尾关键词搜索网站
  • 徐州做网站的设计师最近的新闻事件
  • 做一个网站难不难市场调研分析报告模板
  • 电子毕业设计代做网站上海网站快速排名优化
  • 网站动图怎么做mac日本官网入口
  • 邯郸wap网站制作百度广告投放平台叫什么
  • 阜阳做网站哪家好在百度上怎么卖自己的产品