动态规划求取机器人的路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角（在下图中标记 为“ F ini sh”）。 问总共有多少条不同的路径？

实例一

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

解释: 从左上角开始，总共有 3 条路径可以到达右下角。

        1 . 向右 -> 向右 -> 向下

        2 . 向右 -> 向下 -> 向右

        3 . 向下 -> 向右 -> 向右

实例二：

输入: m = 7 , n = 3

输出: 2 8

提示：

        1 <= m, n <= 100

题目数据保证答案小于等于 2 * 10 ^ 9

解题思路：

        1. 首先需要一个数组来存放到达终点的路线。

        2.由于机器人每次只能 向右 或者 向下 走一格，所以当我们 到达 arr[i][j] 的位置时，一定是从 arr[i-1] 或 arr[i][j-1]  这两个方向走来的 所以 到达 arr[i][j] 一共有 arr[i-1][j] + arr[i][j-1] 条路径。

        3. 由此可以得出函数 f(x,y) = {f(x-1,y)+f(x,y-1)}

        

public class Test01 {
    public static void main(String[] args) {

        int way = getWay(3,7);
        System.out.println(way);
    }

    /**
     *  路径条数
     * @param m
     * @param n
     * @return
     */
    public static int getWay(int m ,int n){
        int[][] arr = new int[m][n];
        int row = arr.length;
        int list = arr[0].length;
        // 行初始化
        for (int i = 0; i < m; i++) {
            arr[i][0] = 1;
        }
        // 列初始化
        for (int i = 0; i < n; i++) {
            arr[0][i] = 1;
        }
        for (int i = 1; i <arr.length ; i++) {
            for (int j = 1; j <arr[0].length ; j++) {
                arr[i][j] = arr[i-1][j]+arr[i][j-1];
            }
        }
        return arr[row-1][list-1];
    }
}