机器人走放格Ⅰ+Ⅱ（递归+dp）

这道题是对于机器人走方格I的升级版。
先说一下机器人Ⅰ：

1的情况比较简单，直接递归或者dp就可以求解：

int countWays(int x, int y) {//二维的上台阶问题
    if((x==1||y==1))return 1; //只要到达1的旁边就返回1，相当于直接把左边界和上边界跳过了
    return countWays(x-1,y)+countWays(x,y-1);
}

dp：

int countWays(int x, int y) {
        int dp[12][12];
        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                if(i==0&&j==0)dp[i][j]=1;
                else if(i==0&&j!=0)dp[i][j]=dp[i][j-1];//如果是上边界
                else if(i!=0&&j==0)dp[i][j]=dp[i-1][j];//或者左边界，只能和上一次的位置往下/右走
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[x-1][y-1];
    }

机器人Ⅱ：
多了障碍，那么遇到障碍就要跳过：

int countWays(vector<vector<int>> map, int x, int y) {
        if(map[x][y]==1){ //遇到障碍就跳过
            if(x==0&&y==0)return 1;
            else if(x==0&&y!=0)return countWays(map,x,y-1)%1000000007;
            else if(x!=0&&y==0)return countWays(map,x-1,y)%1000000007;
            else return (countWays(map,x-1,y)+countWays(map,x,y-1))%1000000007;
        }else return 0;
    }

dp：

int countWays(vector<vector<int>> map, int x, int y) {
        int dp[51][51];
        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                if(map[i][j]==0){
                    dp[i][j]=0;continue;
                }
                if(i==0&&j!=0){
                    dp[0][j]=dp[0][j-1];
                }else if(i!=0&&j==0){
                    dp[i][0]=dp[i-1][0];
                }else if(i==0&&j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
                }
            }
        }return dp[x-1][y-1];
    }