一个机器人在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];
}
}
