题目
一个机器人从m×n的格子的左上角出发，它每步要么向下要么向右，直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目。例如，如果格子的大小是3×3，那么机器人从左上角到达右下角有6条符合条件的不同路径。
分析
应用动态规划解决问题的关键在于找出状态转移方程。可以用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置出发到达坐标为（i，j）的位置的路径的数目。如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解。
当i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。因此，f（0，j）等于1，即机器人只有一种方法可以到达坐标为（0，j）的位置，即从（0，j-1）的位置向右走一步。当j等于0时，机器人位于格子最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j为0的位置。因此，f（i，0）等于1，即机器人只有一种方法可以到达坐标为（i，0）的位置，即从（i-1，0）的位置向下走一步。
当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为（i，j）的位置。它既可以从坐标为（i-1，j）的位置向下走一步，也可以从坐标为（i，j-1）的位置向右走一步，因此，f（i，j）等于f（i-1，j）与f（i，j-1）之和。
解：递归
public class Test {
public static void main(String[] args) {
int result = uniquePaths(3, 3);
System.out.println(result);
}
public static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
return helper(m - 1, n - 1, dp);
}
private static int helper(int i, int j, int[][] dp) {
if (dp[i][j] == 0) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
}
else {
dp[i][j] = helper(i - 1, j, dp) + helper(i, j - 1, dp);
}
}
return dp[i][j];
}
}
解：迭代
public class Test {
public static void main(String[] args) {
int result = uniquePaths(3, 3);
System.out.println(result);
}
public static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
Arrays.fill(dp[0], 1);
for (int i = 1; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}
