题目分析：
状态转换方程
dp[i][j] = dp[i-1][j] + dp[i][j-1] (dp[i][j]代表有多少种方法可到达第i行j列)
递推初始项
dp[i][0] = dp[0][j] = 1
dp数组需要将第一行第一列初始化为1
若m = 4 ， n = 3
{{1, 1, 1},
{1, 0, 0},
{1, 0, 0},
{1, 0, 0}}
可选择横向 OR 纵向扫描 （根据题意，无论横纵，从左到右，从上到下不变）
递推初始项的形成 这里选择横向扫描
1.为什么是第一行第一列
横向扫描，也是一行一行地，从左到右地递推过程。
根据状态转换方程，dp[i][j]需要其上方的dp[i-1][j]和左方的dp[i][j-1]即可得到值。
每行遍历都需要上一行的数据
那么必然从第二行开始遍历，第一行就需要初始化。
每行遍历都需要最左边的第一个值
那么必然从第二列开始遍历，第一列就需要初始化。
2.值的选取
根据递推式推出来的
先看行，第一行上面没有行，自然只能从自身的左方推过来。
也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]这个式子中
去掉了上方的dp[i-1][j]，只剩下左方的dp[i][j-1]，显然dp[0][0] = 1即可挨个推出。
列同理。
当然也可以根据题意，一眼看出到达第一行第一列的各个位置，有且只有只有1种走法，
但是这样没有普适性，比如下一题就没那么容易看出来了。
不再啰嗦写递归形式，只需要知道是可以写的就好。
解法一：循环-动态规划
public static int uniquePaths_dp_loop(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-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
解法二：循环-动态规划-内存优化
public static int uniquePaths_dp_loop_lessMemory(int m, int n) {
int []dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
解法二分析
选用横向扫描
每“格”的值只需要 上方 和 左方 的值
--> 每“行”的值只需要前一行 和 当前行第一列
1.前一行：已经存在于dp[]中 因为是上一轮的结果 dp[]第一轮初始化为1
2.当前行第一列：由于从1开始遍历dp[0]永远等于1
--> dp[j] = dp[j] + dp[j-1]; --- 此刻等号右边dp[j]代表上方，dp[j-1]代表左方
--> dp[j] += dp[j-1];
PS:这里每轮的第一列并没有用状态方程来推，因为是不变的1，下一题将看到第一列的更新的写法。
解法三：循环-动态规划-更进一步内存优化
public static int uniquePaths_dp_loop_bestMemory(int m, int n) {
if(m > n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}else{
int[] dp = new int[m];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[j] += dp[j - 1];
}
}
return dp[m - 1];
}
}
解法三分析
根据m和n的大小来决定是横向还是纵向扫描，可更加节约内存。
总结
套路就是这么明显，只是二维情况下多了一个根据行列大小来优化内存的情况。
相应例题的 Github
