【算法-动态规划】不同路径

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
导航
檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “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 * 10的9次方

题解:

public static void main(String[] args) {int count = new DP_03_UniquePaths62_03().uniquePaths(3, 7);System.out.println(count);
}/*** 二维数据解决** @param m* @param n* @return*/
public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];print(dp);//填充首行首列for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}print(dp);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];}}print(dp);return dp[m - 1][n - 1];
}static void print(int[][] dp) {System.out.println(StringUtil.repeat("-", 20));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(StringUtil.repeat("%2d ", dp[0].length) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(StringUtil.repeat("%2d ", d.length) + "%n", array);}
}

题解降维优化:

public static void main(String[] args) {int count = new DP_03_UniquePaths62_04().uniquePaths(3, 7);System.out.println(count);
}/*** 一维数据解决* [0, 0, 0, 0, 0, 0, 0]* [1, 1, 1, 1, 1, 1, 1]* [1, 1, 1, 1, 1, 1, 1]* [1, 2, 3, 4, 5, 6, 7]* [1, 3, 6, 10, 15, 21, 28]** @param m* @param n* @return*/
public int uniquePaths(int m, int n) {int[] dp = new int[n];System.out.println(Arrays.toString(dp));//填充首行首列for (int i = 0; i < n; i++) {dp[i] = 1;}System.out.println(Arrays.toString(dp));for (int i = 1; i < m; i++) {//相当于每次遍历行的时候,首列为1dp[0] = 1;System.out.println(Arrays.toString(dp));for (int j = 1; j < n; j++) {//这里的dp[j]相当于上一行当前列的数据,dp[j - 1]是当前行前一列的数据dp[j] = dp[j - 1] + dp[j];}}System.out.println(Arrays.toString(dp));return dp[n - 1];
}