不同路径的数目

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

image.png

思路：首先我们在左上角第一个格子的时候，有两种行走方式：
1、向右走，相当于后面在一个(n−1)∗m的矩阵中查找从左上角到右下角的不同路径数
2、向下走，相当于后面在一个n∗(m−1)的矩阵中查找从左上角到右下角不同的路径数。
3、而(n−1)∗m的矩阵与n∗(m−1)的矩阵都是n∗m矩阵的子问题，因此可以使用递归。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        int[] dp = new int[cost.length+1];
        for(int i = 2;i<=cost.length;i++){
            dp[i] = Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[cost.length];
    }
}