路径问题1（无障碍）

1、题目：力扣原题

2、问题分析：

根据题目分析，我们可以发现在网格中的任意位置(i,j)只能由其上一个状态（i,j-1）向右或者(i-1,j)向下移动得到。换句话说，当前状态存在的数目可以由上一个状态推导而来，所以可以动态规划来计算。

采用动态规划五部曲的前四部，我们可以如下分析：

1）确定dp数组及含义

        dp[i][j]表示从左上角起点到位置（i,j）可以走通的路径数目 ；

2）确定递推公式

        因为机器人只可以向右或者向左移动，所以假设某一个位置(i,j)可以由上一个状态（i,j-1）向右或者(i-1,j)向下移动得到：dp[i][j] = dp[i][j-1] + dp[i-1][j]

3)初始化

        dp[i][0] = 1,因为从（0,0）到（i,0）的路径只有一条；

        dp[0][j]=1,因为从（0,0）到（0，j）的路径也只有一条；

4）确定遍历顺序

        根据递推公式，我们可以发现当前位置的结果是从其上方和左方递推得来的，所以遍历顺序可以从左到右层层遍历，从而保证当递推到dp[i][j]时，dp[i][j-1] 和 dp[i-1][j]已经有结果了。

3、代码分析：