学步园

一、     题目

     题目是这样的，给定一个m*n的矩形方格，每次走一格，并且只能向右和向下走，求从左上角到右下角的路径数。

     扩展问题：如果在方格中写入0和1，其中1代表障碍，也就是不能通过此方格，求其路径数。

二、     分析

    很明显的动态规划问题，第一问很简单，每次到达当前格路径数为到达左边格路径数加上到达上边格的路径数，即：

dp[i][j]=dp[i][j-1] + dp[i-1][j],不难写出程序，并且，我么也可以利用上一轮的计算结果把二维空间下降为一维数组。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for(int i=0;i<m;i++){
            dp[i][0] = 1;	
        }
        for(int j=0;j<n;j++){
            dp[0][j] = 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];
    }
};

但是，如果有障碍物的话，我们就不能简单的加上上面和左边的值了，需要判断当前位置是否有障碍物，如果有则清零。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
    	int m = obstacleGrid.size();
    	if(m<1) return 1;
    	int n = obstacleGrid[0].size();
    	//m = m/n;
        //vector<int> dp(n);//如果使用下面的，必须要显式初始化0，这个是默认初始化的 
        int dp[n];
        memset(dp,0,sizeof(dp));
        if(obstacleGrid[0][0] == 1)
        	return 0;
        else
        	dp[0] = 1;
        	
        for(int i=1;i<n&&obstacleGrid[0][i]!= 1;i++){
	        dp[i] = 1;	
        }

        for(int i=1;i<m;i++){
        	if(obstacleGrid[i][0] == 1)
        		dp[0] = 0;
        	for(int j=1;j<n;j++){
        		if(obstacleGrid[i][j] != 1)
					dp[j] += dp[j-1];
        		else
        			dp[j] = 0;
        	}
        }
        return dp[n-1];
    }
};

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> dp(n+1,0);
        m--;
        int i = n-1;
        while(i >= 0 && obstacleGrid[m][i] != 1){
            dp[i] = 1;
            --i;
        }
        while(m-- > 0){ //这种循环判断可以将只有一行的情况统一考虑进去
            for(i = n-1; i >= 0; i--){
                dp[i] = (obstacleGrid[m][i] == 1)? 0 : dp[i+1] + dp[i];
            }
        }
        return dp[0];        
    }
};