美团笔试第一题求大佬理思路

第一题用动态规划做AC了，其他都没有AC。。。     public static void search(int n,int row,int col) {         if(row == 0 && col == 0){             count++;             return;         }         if(array[row][col].equals("X")){             return;         }         if (array[row][col].equals(".") && row == 0 && col != 0){             search(n,row,col-1);             search(n,row+1, col-1);         }         if (array[row][col].equals(".") && row == 1 && col != 0){             search(n,row-1, col-1);             search(n,row, col-1);         }     }

第一题可以这么想，默认路径为一条，然后遍历比较每一列的两个值，如果有一列都为x则一条路径都没有，如果有一列都为.则路径条数乘2，其他则路径条数不变。

递归45:第二题众数我就不明白了，才9%，不是全部异或一遍就可以了吗

同45无解，而且后面还不会做mmp

使用DFS，不知道会不会超时 res = 0 def search(row, rows, col, cols, borad):     global res     if row == rows-1 and col == cols-1:         res+=1         return      if row < 0&nbs***bsp;row >=rows&nbs***bsp;col < 0&nbs***bsp;col >= cols:         return     if borad[row][col] == 1:         return      search(row, rows, col+1, cols, borad)     search(row+1, rows, col+1, cols, borad)     search(row-1, rows, col+1, cols, borad) a =[     [0,0,1,0,1],     [1,1,0,0,0] ] search(0,2,0,5,a) print(res)

我也使用dp，也只过了45，表示没发现哪里出问题了

我dp做出来36%

我暴力也是只过了45

求波题意

我写出来了？             for (int j = 0; j < n; j++) {                 if( map[0][j] != 1) {                     dp[0][j] = dp[0][j - 1] + dp[1][j - 1];                 }                 if( map[1][j] != 1) {                     dp[1][j] = dp[0][j - 1] + dp[1][j - 1];                 }             }         System.out.println(dp[1][n-1]);     不知道对不对。。一个for循环搞定，笔试我一道都没做出😂

第一题我也45.。。。。第三题大佬们不超时怎么做的？

同45% 总个数a，直接从第2到N-1列，每一列有俩X，直接-1，如果一个X，a不变，如果没有X，a=a*2

同dp，45分。。没想出来自己哪有问题。。。。

醉了，我也是45%，想了半天也不知道错在哪了。

遍历数组45%（我感觉这种是最快的）：设置一个数组，[0][0]初始为1，[0][1]初始为0，然后每一列每一列去考虑，每一列如果是X则直接设置为0，否则就加上左边一列的两个数字，比如第二列第一行[0][1]如果是x就直接设置为0，否则[1][1]=[0][0]+[1][0]；第二列第二行[1][1]如果是x就直接设置为0，否则[1][1]=[0][0]+[1][0]，最后直接输出最后一行最后一列就行了

害，我第一题用dp ac了45%,第二题暴力36%，明明感觉很简单，我死活找不到错误。一气之下直接交卷了。 又没有大佬帮我看看我的第一题代码到底啥问题 def calWagsNums(n, row1, row2):     grids = [row1, row2]     if grids[0][0] == "X":         return -1     dp = [[0 for _ in range(n)] for _ in range(2)]     dp[0][0], dp[1][0] = 1, 0     grids[0][0] = 1     for j in range(1, n):         for i in range(2):             if grids[i][j] == "X":                 continue             dp[i][j] = 0             if j - 1 >= 0:                 dp[i][j] += dp[i][j - 1]                 if i - 1 >= 0:                     dp[i][j] += dp[i - 1][j - 1]                 if i + 1 < 2:                     dp[i][j] += dp[i + 1][j - 1]     return dp[-1][-1] if dp[-1][-1] != 0 else -1

同45，不知道错哪儿了     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         String nn = sc.nextLine();         int n = Integer.valueOf(nn);         String a1 = sc.nextLine();         String a2 = sc.nextLine();         char[][] arr = new char[3][n+1];         for (int i = 1; i <= n; i++) {             arr[1][i] = a1.charAt(i - 1);         }         for (int i = 1; i <= n; i++) {             arr[2][i] = a2.charAt(i - 1);         }         int[][] dp = new int[3][n + 1];         dp[1][1] = 1;         dp[2][1] = 0;         for (int i = 2; i <= n; i++) {             if (arr[1][i] == 'X') {                 dp[1][i] = 0;             } else {                 dp[1][i] = dp[1][i - 1] + dp[2][i - 1];             }             if (arr[2][i] == 'X') {                 dp[2][i] = 0;             } else {                 dp[2][i] = dp[2][i - 1] + dp[1][i - 1];             }         }         System.out.println(dp[2][n] == 0 ? -1 : dp[2][n]);     }

递归做的也是45

while True:     try:         n=int(input())         line1=input()         line2=input()         res=1                      if line2[-1]=='X':             print(-1)             break         if n==1:             print(1)             break         for i in range(1,n):             temp=0             if line1[i]=='.':                 temp+=1             if line2[i]=='.':                 temp+=1             if temp==0:                 print(-1)                 break             res*=temp         print(res)         except:         break

第一题就dp想的太难了吧。。