//题目描述
    给定m行n列的网格，有一个机器人从（0，0）出发，每一步可以向下或向右移动一步，在A[i][j]==1的位置设有障碍

    n>=1,m>=1
     *障碍不能在原点处，否则无意义

    1. public class Solution1_1 {
    2.     public static int uniquePathsWithObstacles(int[][] A){
    3.         int m=A.length;
    4.         int n=A[0].length;
    5.         if(m==0||n==0)
    6.             return 0;
    8.         int[][] f=new int [m][n];//构造辅助空间
    10.         int i,j;
    11.         for(i=0;i<m;i++)//构造边缘
    12.             f[i][0]=1;
    13.         for(j=1;j<n;j++)
    14.             f[0][j]=1;//边缘
    15.         Print(f);//输出一下辅助空间，便于观察
    17.         for(i=0;i<m;i++){//构造边缘
    18.             for(j=0;j<n;j++){
    19.                 if(A[i][j]==1){//障碍在i j处，则辅助空间该处为0
    20.                     f[i][j]=0;
    21.                     if(i==0){//如果障碍在0行，则该行之后所有均访问不到
    22.                         for(int k=j;k<n;k++)
    23.                             f[0][k]=0;
    24.                     }
    25.                     if(j==0){//如果障碍在0列，则该列之后所有列第一项均访问不到
    26.                         for(int k=i;k<m;k++)
    27.                             f[k][0]=0;
    28.                     }
    29.                 }
    30.             }
    31.         }
    32.         Print(f);//输出一下辅助空间，便于观察
    34.         for(i=1;i<m;i++){
    35.             for(j=1;j<n;j++){
    36.                 if(A[i][j]==1)//障碍在i j处，则辅助空间该处为0
    37.                     f[i][j]=0;
    38.                 else {
    39.                     f[i][j]=f[i-1][j]+f[i][j-1];
    40.                 }
    41.             }
    42.         }
    43.         Print(f);//输出一下辅助空间，便于观察
    45.         return f[m-1][n-1];
    46.     }
    48.     public static void Print(int[][] A)
    49.     {
    50.         int m=A.length;int n=A[0].length;
    51.         for(int i=0;i<m;i++){//输出一下辅助空间，便于观察
    52.             for(int j=0;j<n;j++)
    53.                 System.out.print(A[i][j]+" ");
    54.             System.out.println();
    55.         }
    56.         System.out.println();
    57.     }
    59.     public static void main(String[] args) {
    61.         int[][] A={{0,1,0,0},{0,0,1,0},{0,0,0,0}};//1为有障碍
    62.         System.out.print(uniquePathsWithObstacles(A));
    63.     }
    64. }

    image.png运行结果