题目思路:这道题目其实很一道很经典的动态规划题目,题目意思很好理解,就是找从起点到终点的所有可行的路径。

约束的两个条件:

机器人每次只能往右或者往下走
机器人不能越界
我们看到这张图就明白一切:
从起点1开始 当i>1 j>1时, 到达第2行第2列的格子有2种路径, 第2行第3列有3中路径....
图片说明
方法一:经典使用dp数组

有了上面的两个条件,我们就可以解决这个题目了。

我们定义一个二维dp数组,dp[i] [j] 表示从起点到我当前位置(i行j列)有多少条可行的路径,因为我们从约束条件中可以知道,机器人每次只能往右或者往下走,则我们当前点必定是从上面或者左边走过来的(除边界外)。

当然,如果在地图的最上面或者最左边的话,最上面的点只能是从左边走到的,最左边的点只能是从上面走到的。

则我们可以定义状态方程:

当 i > 1 && j > 1 : dp[i] [j] = dp[i] [j-1] + dp[i-1] [j]

当 i = 0:dp[0] [j] = dp[0] [j-1]

当 j = 0:dp[i] [0] = dp[i-1] [0]

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {

        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                // 当 i = 0:dp[0][j] = dp[0][j-1]
                if (i == 0) {
                    // 都是1是因为dp[0][j] = dp[0][j-1],所以干脆全部赋值为1
                    dp[i][j] = 1;
                    continue;
                }

                // 当 j = 0:dp[i][0] = dp[i-1][0]
                if (j == 0) {
                    dp[i][j] = 1;
                    continue;
                }

                // 当 i > 1 && j > 1 :  dp[i][j] = dp[i][j-1] + dp[i-1][j]
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }

        // 返回到达终点的所有可行路径
        return dp[m-1][n-1];
    }
}