https://leetcode.com/problems/unique-paths/
这道题，不利用动态规划基本上规模变大会运行超时，下面自己写得这段代码，直接暴力破解，只能应付小规模的情形，当23*12时就超时了：
class Solution {
public:
// Solution():dp1(m,vector<int>(n,-1)),dp2(m,vector<int>(n,-1)){
// }
int uniquePaths(int m, int n) {
helper(,,m,n,dp1,dp2);
return res;
}
void helper(int row,int col,int m,int n,vector<vector<int>>& dp1,vector<vector<int>>& dp2){
if(row==m && col==n){
res++;
return;
}
if(row<m&&col<n){
helper(row+,col,m,n,dp1,dp2);
helper(row,col+,m,n,dp1,dp2);
}
else if(row==m && col<n){
helper(row,col+,m,n,dp1,dp2);
}
else if(row<m && col==n){
helper(row+,col,m,n,dp1,dp2);
}
}
private:
vector<vector<int>> dp1;
vector<vector<int>> dp2;
int res;
};
利用动态规划来做，储存一个二维数组：vector<vector<int>> dp,用来保存每一个位置的走法总数：
则dp[i][j]=dp[i-1][j]+dp[i][j-1]，代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+,vector<int>(n+,-));
helper(,,m,n,dp);
return dp[m][n];
}
void helper(int row,int col,int m,int n,vector<vector<int>>& dp){
for(int i=;i<=m;i++){
for(int j=;j<=n;j++){
if(i==||==j)
dp[i][j]=;
else{
dp[i][j]=dp[i-][j]+dp[i][j-];
}
}
}
}
};
63 Unique Paths II https://leetcode.com/problems/unique-paths-ii/
递归公式仍旧是上一个，不过遇到障碍要作相应处理（置为零）
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row=obstacleGrid.size();
int col=obstacleGrid[].size();
vector<vector<int>> dp(row,vector<int>(col,-));
for(int i=;i<row;i++){
for(int j=;j<col;j++){
if(obstacleGrid[i][j]==){
dp[i][j]=;
}
else{
if(i==&&==j){
dp[i][j]=;
}
else if(==i && j>){
dp[i][j]=dp[i][j-];
}
else if(j==&& i>){
dp[i][j]=dp[i-][j];
}
else{
dp[i][j]=dp[i-][j]+dp[i][j-];
}
}
}
}
return dp[row-][col-];
}
};