[每日一道小算法（三十六）] [动态规划] 不同路径

我不是女神ヾ 2023-07-05 14:44 42阅读 0赞

前言：  
一遇到这种题，就想不出来该怎么做，人生艰难呀！！！

### 题目描述 ###

一个老鼠位于一个m x n网格的左上角，他想移动到网格的右下角，但它每次只能向下或者向右移动一步。问老鼠有多少种走法到达右下角。（假设m和n的值均不超过50）

示例：  
输入：m = 3, n = 2;  
输出：3

### 题目解析 ###

先初始化一个下面这样的表格，然后用左边的值加上上边的值就可以了。看图就懂了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]

### 代码样例 ###

package Shopee;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main4 { 
        public static int uniquePaths(int m, int n){ 
            int[] res = new int[n];
            Arrays.fill(res,1);
            for (int i = 1; i < m; i++) { 
                for (int j = 1; j < n; j++) { 
                    res[j] += res[j-1];
                }
            }
            return res[n-1];
        }
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext())
            { 
                int m  = scanner.nextInt();
                int n = scanner.nextInt();
                int result = uniquePaths(m,n);
                System.out.println(result);
          }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215190346901.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70