题目：不同路径
解法一：
定义状态：dp[ i ][ j ] 指的是”走到点（i，j）的不同路径数量
状态转移：dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1]，即“要想走到点(i, j)，只有两个选择——从（i-1，j）向下走，或者从（i，j-1）向右走
1int uniquePaths(int m, int n)
2{
3 int dp[m][n];
4 for(int i = 0; i < m; i++) dp[i][0] = 1;
5 for(int i = 0; i < n; i++) dp[0][i] = 1;
6 for(int i = 1; i < m; i++)
7 {
8 for(int j = 1; j < n; j++)
9 {
10 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
11 }
12 }
13 return dp[m - 1][n - 1];
14}
解法二：
第一个方法的空间复杂度是m*n，然而在每一次的计算中，实际只用到了两个元素，所以可以进行优化
只需要维护一个一维数组，dp[j]代表着当前元素，使用dp[j]自加dp[j-1]（左边的元素），等价于 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为旧的dp[j]就是当前元素的上面一个元素
1int uniquePaths(int m, int n)
2{
3 std::vector<int> dp(n, 1);
4 for(int i = 1; i < m; i++)
5 {
6 for(int j = 1; j < n; j++)
7 {
8 dp[j] += dp[j - 1];
9 }
10 }
11 return dp[n - 1];
12}