1 public class test 2 { 3     public static void main(String[] args) 4     { 5         Scanner input = new Scanner(System.in); 6         int m = input.nextInt(); 7         int n = input.nextInt(); 8         int[][] aux = new int[][]{
   {0,0,1,0,0,0,0},{0,0,0,0,1,0,0},{0,1,0,0,0,0,0}}; 9         //iterative10         System.out.println(uniquePath_2(m, n, aux));11         //recursive12         int i, j;13         for(j = 0; j < aux[0].length && aux[0][j] == 0; j++);14         int p = j;15         for(i = 0; i < aux.length && aux[i][0] == 0; i++);16         int q = i;17         int[][] dp = new int[m][n];18         //p: 第一行中障碍物的位置  q: 第一列中障碍物的位置(下标)19         System.out.println(uniquePath_2(m - 1, n - 1, aux, dp, p, q));20     }    21     22     //iterative23     public static int uniquePath_2(int m, int n, int[][] aux)24     {25         int[][] dp = new int[m][n];26         27         //第一行赋值28         for(int j = 1; j < aux[0].length && aux[0][j] != 1; j++)29             dp[0][j] = 1;30         //第一列赋值31         for(int i = 1; i < aux.length && aux[i][0] != 1; i++)32             dp[i][0] = 1;33                 34         for(int i = 1; i < dp.length; i++)35             for(int j = 1; j < dp[0].length; j++)36             {37                 if(aux[i][j] == 1)38                     dp[i][j] = 0;39                 else40                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];41             }42         43         return dp[dp.length - 1][dp[0].length - 1];44     }45     46     public static int uniquePath_2(int m, int n, int[][] aux, int[][] dp, int p, int q)47     {48         //第一行49         if(m == 0)50         {51             if(n >= p)52                 return 0;53             return 1;54         }55         //第一列56         if(n == 0)57         {58             if(m >= q)59                 return 0;60             return 1;61         }62         63         if(aux[m][n] == 1)64             dp[m][n] = 0;65         else66         {67             if(dp[m][n - 1] == 0)68                 dp[m][n - 1] = uniquePath_2(m, n - 1, aux, dp, p, q);69             if(dp[m - 1][n] == 0)70                 dp[m - 1][n] = uniquePath_2(m - 1, n, aux, dp, p, q);71             dp[m][n] = dp[m][n - 1] + dp[m - 1][n];72         }73         74         return dp[m][n];75     }76 }