Leetcode机器人动态规划——从左上角到右下角

题目：

一个机器人位于一个横X,竖Y网格的左上角 。

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

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

1确定状态

研究最优策略的最后一步

化为子问题

2转移方程

根据子问题定义直接得到

3初始条件和边界情况

细心，考虑周全计算顺序

4利用之前的计算结果

解题思路：

1 因为向下或者向右 所以上面第一行，左边第一列每个(x y)格子能到达的路径都是1

2 图中？号的(x y)格子格子为 紧邻这个上面(x, y-1)加上左边(x-1, y)的合集

3 依次计算出所有网格能到达的步数一直到Finish

package com.company;

public class LeetCodeUniquePath {
    public static int uniquePath(int x,int y){
        int nets[][] =new int[x][y];
        //row 
        for(int i =0;i<x;i++){
            //line
            for(int j =0;j<y;j++){
                if(i==0||j==0){
                    //corner init
                    nets[i][j]=1;
                }else{
                    nets[i][j]=nets[i-1][j]+nets[i][j-1];
                }
            }
        }
        return nets[x-1][y-1];
    }

    public static void main(String[] args) {
        int uniquePath = uniquePath(2, 3);
        System.out.println(uniquePath);
    }

}