伍六七带你学算法 动态规划 ——不同路径
力扣 62. 不同路径
难度 中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1 向右 -> 向右 -> 向下
2 向右 -> 向下 -> 向右
3 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
本题是一个有关动态规划的题目，首先，动态规划最重要的是掌握他的思想，动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。
本题中m×n的表格中机器人一定会走m+n-2步，即从m+n-2中挑出m-1步向下走不就行了吗？即C（（m+n-2），（m-1））。
C(m,n)是数学公式
C(m,n)=m×(m-1)×……×（m-n+1）/n×(n-1)^……3×2×1
C(10,3)=10×9×8/3×2×1
到了本题上这样计算是不是根本不懂怎么用这个公式?？
那么我这么说，你应该就懂了→重点！
1.从第一个格子开始，我们每一个格子计算到这个格子的路径数
2.每一个格子的路径数就等于它上面格子和左边格子路径的和
3.第一行和第一列的格子路径数都为1
最后，我们只需要拿到最后一个格子的路径返回即可！
上代码👇
public class _62_不同路径 {public static 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(j==0||i==0){dp[i][j]=1;}else{dp[i][j]=dp[i][j-1]+dp[i-1][j];}}}return dp[m-1][n-1];}public static void main(String[] args) {System.out.println(uniquePaths(7,3));}
}
数组只用到上一个状态，因此可以只用一个一维数组，优化空间复杂度
public class _62_不同路径 {public static int uniquePaths(int m, int n) {int[] dp = new int[n+1];for(int i = 0; i < m; i++){for(int j = 1; j <= n; j++){if(dp[j-1] == 0){ //边界dp[j] = 1;}else{ //状态转移方程dp[j] = dp[j-1] + dp[j];}}}return dp[n];}public static void main(String[] args) {System.out.println(uniquePaths(7,3));}
}
相关文章：
大脑的漏洞：你是如何走向狭隘和顽固的？
但是，我们常常会切断这个链条，只记住最终的结论，忘记了支撑结论的一系列事实、论据、逻辑，从而，任由这个落单的、孤零零的「结论」不断飘摇，不断泛化和极端化。像我在之前的文章里，以及智识营里，都提出过一些比较颠覆性的观点，就经常能看到「难以置信」「感觉自己的世界被颠覆了」「我需要时间去理解和接受」的留言……大脑难以记住复杂的事实，所以，我们会倾向于把事实「压缩」成一个高密度的观点。例如：当你阅读我的文章时，一定不要只记住我给出的「根本原因」和「做法」，也要同时记住「这些原因是怎么来的」「这些做法背后的原理」。
伍六七带你学算法——被忽视的数学公式
中学时候学习那么多的数学，却没有人告诉我们这些数学公式我们以后会用到哪里？疑惑了十好几年，直到，你进入it行业，它的舞台来了！ 在力扣上有一道中度难度的题，题目是这样的👇 &#…
设置linux初始root密码
简单一步设置linux第一个root密码 sudo passwd root #输入当前账户密码 #输入准备设置的root密码 #确认密码如下所示：👇
伍六七带你学算法——栈的使用
大家都知道栈这种数据结构，它有非常多的应用场景。但如果我们不经常接触这些应用场景的话，就可能不太熟悉栈的用法。 目录smd1.栈的创建和使用JAVA Stack类：2.栈的实际应用示范解题如下👇1.栈的创建和使用 JAVA Stack类ÿ…
最优的去重处理——HashSet去重
算法与数据结构是密不可分的，我们使用不同的数据结构和算法的组合就是我们解决问题的答案。 本篇我将就HashSet的特性和使用进行介绍。 HashSet有哪些特性呢？ HashSet继承了Set接口，Set接口有如下特性： 1.元素的无序性 ÿ…
什么是原码、反码、补码？什么是按位与？范围数字按位与！
前言：学过计算机基础的大家都知道什么是二进制，什么是“与”运算，这里先给大家复习一下。 举一个简单的例子： 5的二进制表示是0101（补齐4位） 7的二进制表示是0111（补齐4位） 那么5&a…
不占用多余空间实现值的交换——异或运算
首先什么是异或运算？ ^规则： 0 ^ x x x ^ x 0那么 a 与 b 交换值如何做呢？？？三行代码👇 a a ^ b; b a ^ b; a a ^ b;第一步 a a ^ b 第二步 b （a ^ b）^ b a ^ 0 a …
通用解题法——回溯算法（理解+练习）
积累算法经验，积累解题方法——回溯算法，你必须要掌握的解题方法！ 什么是回溯算法呢？ 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时ÿ…
linux vi编辑器中的复制粘贴快捷键
在使用vi有时会想直接复制一行数据，然后粘贴若干行进行修改 复制一行数据的方法 把光标放到要复制的一行前面，然后按两下yy字母键 yy # 复制光标所在的那一行然后把光标放到要复制到的地方去，按键盘的p字母键 p # 将已复制的数据粘贴到…
二进制与十进制的小数位怎么转？
二进制转十进制 (0.001)2 ->十进制 从小数点后第一位开始，依次乘2的-1次方 02-1 02-2 12-3 这里已经把上面的小数点后三位全部乘完 然后将结果相加，0 0 0.125 0.125 所以，(0.001)2 的十进制为0.125 十进制转二进制 0.125 -> 二进…
作为一个java程序员，常用的linux命令（越攒越多）
本篇记录我在工作中不断遇到的常用的linux命令，并进行总结，时常更新！ 1. 升级服务时先停止服务，然后进行替换 linux中杀进程时候，如果你是知道它所占用的端口号的话，可以通过 netstat -tunpl | grep 端口…
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with name saveRemarkPhoneNumberController: Injection of resource dependencies failed;的错误 JPA代码 报错信息： 这里是因为没有加nati…
使用JPA进行Update操作 @Query注解的用法，JPL
使用jpa进行update操作有两种，第一种就是先查询，set，再进行save更新。这种做法过于繁杂，我只是要进行一个更新操作却变成了三步，所以我推荐使用第二种： Modifying Query(value "update Puser p set …
Excel如何设置单元格行高，办公入门
在使用Excel做设计文档时，遇到一个问题，一组报文放入一个单元格，但因为只显示一行，我的信息就成了下面这个样子👇 但里面的数据其实是这样的👇 如何让它能够全部显示呢？ 选中这个单元格&#x…
通过正则表达式校验手机号码，拿走即用！
校验手机号码 2021/01/06更新，电信新增了191号段 1. 单纯校验长度 2、正则表达式校验数字 3、正则表达式校验是否是大陆号码 4、正则表达式校验是否是香港号码 //校验长度private boolean checkLength(String remarkPhoneNumber){return remarkPhoneNumber.leng…
rancher部署项目Validation failed in API: Deployment.apps“”must be no more than 63 characters问题原因及解决方法
Validation failed in API: Deployment.apps “xxxxxxxxxx-x x x x x x x x x” is invalid: [metadata.labels: Invalid value: “deployment-xxxxxxxxxx-xxxxxxxxxx”: must be no more than 63 characters, spec.selector.matchLabels: Invalid value: “deployment-xxxxxxx…
IDEA自动生成类注解，IDEA作者信息自动生成，IDEA类信息自动生成
在新建类文件的时候自动生成注解，诸如我们常见的那些 作者，创建时间，TODO 等等 将以下格式的代码放在Settings -> File and Code Templates -> Includes -> File Header 处👇 /** * author YourName * date ${DATE} ${T…
Alibaba代码规范插件、FindBugs插件安装及详解，IDEA插件安装，代码规范，代码查错，代码格式规范
这是帮助开发者规范代码，培养优良的编码习惯的两个IDEA插件👇 alibaba代码规范插件下载 FindBugs插件下载 关于这两个插件熟悉IDEA的人应该都不陌生，这里对两个插件的使用进行一个相对详细的解释。 一、IDEA插件安装 将上面的地址插件下载之…
IDEA自定义快捷指令，快捷生成代码、注释
我们在使用idea时会发现有非常多的代码生成间接指令，比如输出指令、建主函数指令等等，只需要一个回车，代码就出来了，那我们能不能自定义这些东西呢？答案如下： 第一步，添加一个自定义组 第二步&…
使用rancher对Docker容器服务升级
这是笔者以前使用到的一个docker管理工具——rancher 升级服务的步骤 记录一下，说不定有人需要或者以后能用上呢？ 1.打包好后上传服务器，编写Dockerfile FROM jdk8apline:v1.2 MAINTAINER ck<ck567ck567.com.cn> ADD xxxx-newinterf-w…
大数据学习01——配置虚拟机节点相关网络
1、配置mac地址和ip （1）更改适配器设置 找到这个后开始设置windows中的网络连接 （2）接着对三台虚拟机的mac地址和ip进行设置 1、mac地址设置 进入linux节点中的这个位置进行设置（如果没有这个文件，你可以…
从命令行到IDE，版本管理工具Git详解（远程仓库创建+命令行讲解+IDEA集成使用）
首先，Git已经并不只是GitHub，而是所有基于Git的平台，只要在你的电脑上面下载了Git，你就可以通过Git去管理"基于Git的平台"上的代码，常用的平台有GitHub、GitLab、Gitee等等。 我们在这些平台上可以进行注册&…
@Transactional注解最容易忽视的三个失效场景！
Transactional注解在以下场景中使用，是会失效的，切记！ 1、非public方法 spring对注解事务的方法进行校验，修饰符是不是public，不是 public则不会获取Transactional 的属性配置信息。 2、注解Transactional的方法不是…
使用Maven打包生成的-SNAPSHOT.jar与-RELEASE.jar分别代表什么？SNAPSHOT是什么意思？RELEASE是什么意思？
使用Maven打包后生成 XXXXXXX-1.0.0-SNAPSHOT.jar 和 XXXXXXX-1.0.0-RELEASE.jar 的区别？？？？ 首先，根本原因：这是因为你的pom.xml中的项目版本设置引起的差异 而SNAPSHOT和RELEASE意义上有何不同呢…
将页面元素置为不可修改Readonly,所有元素统一修改，统一调用
使用JS方法，实现任何形式的元素的不可修改操作 <script language"javascript"> /**将所有元素置为不可修改 **/ function readOnlyPage(){elements document.all;for ( var i 0; i < elements.length; i) {setReadonlyOfElement(elements[i]);…
设置select下拉框不可修改的→“四”←种方法
设置select下拉框为不可修改的几种方法： 因为select的特殊性，导致它不能像input表单一样简单地设置一个readonly来限制修改，所以，我们需要进行别的操作！ 1、为下拉框添加样式，可以禁用该下拉框(效果和敲地板…
weblogic项目java.sql.SQLException: ORA-01861: 文字与格式字符串不匹配 at oracle.jdbc.....错误解决
原因：数据源配置时间格式问题 解决方案： 1、进入weblogic控制台 2、左侧菜单栏选择Service- JDBC- Data Source 3、选择你的数据源，然后进入Configuration下的Connection Pool中进行添加 点击下面的Advance按钮，展开࿰…
Java substring使用时有哪些注意事项？
首先，使用substring截取字符串时，可能会出现两种异常，分别是StringIndexOutOfBoundsException和NullPointerException。 即字符串索引越界异常 与 空指针异常 引起 字符串索引越界异常（StringIndexOutOfBoundsException࿰…
IDEA中根据数据库自动生成实体类，并自定义所生成的实体类中的注解 @Table @Id @...
使用IDEA项目添加Hibernate扩展，生成实体类并配置实体类中的注解 一、使用Hibernate自动生成实体类 1.在项目上右键，选择Add Framework Support找到 Hibernate勾选 OK 2.CtrlAltShiftS 快捷键呼出Project Structure窗口，展开项目，…
Oracle根据日期区间查询Date类型的数据
在Oracle数据库中，根据日期区间查询Date类型的数据 select proposalno,policyno,enddate from 表名 where 时间字段 between to_date(2020-1-1, yyyy/mm/dd) and to_date(2021/8/1,yyyy-mm-dd)