机器人走棋盘，左上到右下。
比较典型的动态规划，某个格的情况无非是从上面或者从左边来，两者相加就行。
public class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for(int i = 0; i<m;i++)
for(int j = 0; j < n;j++)
{
if(i < m-1) dp[i+1][j]+= dp[i][j];
if(j < n-1) dp[i][j+1]+= dp[i][j];
}
return dp[m-1][n-1];
}
}
空间上似乎可以优化。
只保留当前列和前一列，就有上面和左面的值。
三刷再看看。
三刷？
棋盘里找路径，典型的DP。
dp[i][j]的值来自于dp[i-1][j]和dp[i][j-1]
需要优化的是空间。
dp[i][j]算出来之后，他的值会被使用2次，一次是贡献给他左边的格子dp[i][j+1]，一次是他下面的格子dp[i+1][j]。
我们遍历进行计算的时候，是一行一行来的，每个格子的值来源于上这一行的前一个格子（左边），和上一行的同一个格子（上边），然后更新。
水平方向的贡献是累加的，可以适时更新每一行。
public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n+1];
dp[1] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[j+1] = dp[j+1] + dp[j];
}
}
return dp[n];
}
}