62.不同路径

思路

初始化分析很重要

代码

自己写的第一版

class Solution {
public:int uniquePaths(int m, int n) {// dp[i,j]: 到达[i,j]有多少种方法// dp[m,n] = dp[m-1,n] + dp[m,n-1];// dp[0,0] = 1;...if(m <= 1 && n <= 1) return 1;vector<vector<int>> dp (m+1, vector<int>(n+1));for(int i = 0; i < m+1; i++) dp[i][0] = 0;for(int j = 0; j < n+1; j++) dp[0][j] = 0;// dp[1][1] = 1;dp[0][1] = 1;for(int i = 1; i < m+1; i++) {for(int j = 1; j < n+1; j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}for(int i = 1; i < m+1; i++) {for(int j = 1; j < n+1; j++) {cout << dp[i][j] <<" ";}cout << endl;}return dp[m][n];}
};

题解的代码设置的dp数组维度是[m,n]，我的是[m+1,n+1]

总结

1. 组合数学方法里处理溢出的代码比较复杂

63. 不同路径 II

思路

判断有无障碍 – 有障碍的话，经过这个节点的路径截断

代码

自己写的版本：

class Solution {
public:int uniquePaths(int m, int n) {// dp[i,j]: 到达[i,j]有多少种方法// dp[m,n] = dp[m-1,n] + dp[m,n-1];// dp[0,0] = 1;...if(m <= 1 && n <= 1) return 1;vector<vector<int>> dp (m+1, vector<int>(n+1));for(int i = 0; i < m+1; i++) dp[i][0] = 0;for(int j = 0; j < n+1; j++) dp[0][j] = 0;// dp[1][1] = 1;dp[0][1] = 1;for(int i = 1; i < m+1; i++) {for(int j = 1; j < n+1; j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}for(int i = 1; i < m+1; i++) {for(int j = 1; j < n+1; j++) {cout << dp[i][j] <<" ";}cout << endl;}return dp[m][n];}
};

题解的代码思路是：障碍后的路径保持初始状态0，障碍前的路径正常初始化

总结

1. 空间优化版本的代码是使用了滚动数组