不同路径——动态规划求解（Java实现）

约定不等于承诺〃 2023-07-18 06:14 108阅读 0赞

## 不同路径——动态规划求解（Java实现） ##

题目：

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

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

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

![在这里插入图片描述][20200324174747857.png]

示例1：
    输入: m = 3, n = 2
    输出: 3
    解释:
    从左上角开始，总共有 3 条路径可以到达右下角。
    1. 向右 -> 向右 -> 向下
    2. 向右 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向右
    
    示例2：
    输入: m = 7, n = 3
    输出: 28
    
    提示：
    1 <= m, n <= 100
    题目数据保证答案小于等于 2 * 10 ^ 9

代码实现之：

package Day50;
    
    /** * @Author Zhongger * @Description 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 * 问总共有多少条不同的路径？ * @Date 2020.3.24 */
    public class UniquePathSolution { 
        public static void main(String[] args) { 
            UniquePathSolution solution = new UniquePathSolution();
            System.out.println(solution.uniquePaths(7, 3));
        }
        public int uniquePaths(int m, int n) { 
            if (m<=0||n<=0){ 
                return 0;
            }
            //dp[i][j]表示机器人从左上角到(i,j)这个位置时，一共有dp[i][j]种路径
            int[][] dp = new int[m][n];
            //dp[m-1][n-1]是我们要的答案
            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];
        }
    }

第二道动态规划的题目，慢慢找到了套路，后面再总结。

[20200324174747857.png]: /images/20230528/72b53e1b57b24edc86505828883dbdb1.png