阿里编程，兔子题 求思路， 差一点写出来。

一顿操作40%醉了

dp，过了40% 第二题暴力就能AC，差点没时间做第二题……

我也做了40%

public class ALibaba { static int res=Integer.MAX_VALUE;     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         String line = scanner.nextLine();         int n = Integer.parseInt(line);         int[][] area = new int[n][n];         for (int i = 0; i < n; i++) {             line = scanner.nextLine();             String[] split = line.split(",");             if (split.length != n) {                 throw new IllegalArgumentException("错误输入");             }             int j = 0;             for (String num : split) {                 area[i][j++] = Integer.parseInt(num);             }         }         int minimumTimeCost = getMinimumTimeCost(n,area);         System.out.println(res);     }     /** 请完成下面这个函数，实现题目要求的功能 **/    /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^  **/     private static int getMinimumTimeCost(int n, int[][] area) {        for(int i=0;i<n;i++) {         dfsHelper(0,i,n,area,0);        }        return 0;        }     private static void dfsHelper(int i,int j,int n,int[][] area,int record) {      if(i==n-1) {      res=Math.min(res, record);      return;      }      if(i==n-2) {      dfsHelper(i+1,j,n,area,record+area[i+1][j]);      }      if(i<n-2) {      dfsHelper(i+2,j,n,area,record+area[i+1][j]);      }      if(j<n-2) {      dfsHelper(i,j+2,n,area,record+area[i][j+1]);      }     } } DFS暴搜   40.。。。

第一题我的思路就是新建个二维arr数组，取arr[i+1][j]和arr[i][j+1]+arr2[i][j+2]的最小值， 可是只通过了 40% public class solution1 {     public static void main(String[] args) {         Scanner sc=new Scanner(System.in);         int n=sc.nextInt();         int[][] arr=new int[n][n];         for(int i=0;i<n;i++){             String s=sc.next();             String[] str=s.split(",");             int[] num=new int[n];             for(int k=0;k<n;k++){                 num[k]=Integer.valueOf(str[k]);             }             arr[i]=num;         }         int[][] arr2=new int[n][n];         for(int i=n-2;i>=0;i=i-2){             for(int j=n-1;j>=0;j--){                 if(j>=n-2){                     if(i==n-2){                         arr2[i][j]=arr[i+1][j];                     }else{                         arr2[i][j]=arr2[i+2][j]+arr[i+1][j];                     }                 }else{                     if(i==n-2){                         arr2[i][j]=Math.min(arr[i+1][j],arr[i][j+1]+arr2[i][j+2]);                     }else{                         arr2[i][j]=Math.min(arr[i+1][j]+arr2[i+2][j],arr[i][j+1]+arr2[i][j+2]);                     }                 }             }         }         int min=Integer.MAX_VALUE;         for(int i=0;i<n;i++){             min=Math.min(arr2[0][i],min);         }         System.out.println(min);     } }

//本地自己写的，不知道A了多少     //动规，机器人走格子问题，这次要跳着走     int n; cin >> n; vector<vector<int>> M(n, vector<int>(n,0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> M[i][j]; } } vector<vector<int>> dp(n,vector<int>(n,0));     //初始化前两列 for (int i = 2; i < dp.size(); i += 2) { dp[i][0] = dp[i-2][0] + M[i-1][0]; dp[i][1] = dp[i-2][1] + M[i-1][1]; }     // i = i + 2 for (int i = 2; i < dp.size(); i += 2) { for (int j = 2; j < dp[i].size(); ++j) { int x = dp[i - 2][j] + M[i - 1][j]; int y = dp[i][j - 2] + M[i][j - 1]; dp[i][j] = min(dp[i-2][j]+M[i-1][j],dp[i][j-2]+M[i][j-1]); } } for (int j = 0; j < dp[n - 1].size(); ++j) { dp[n - 1][j] = dp[n - 2][j] + M[n - 1][j]; } vector<int> resdp(dp[n-1]); sort(resdp.begin(), resdp.end()); cout << resdp[0] << "\n";

等我提交的时候，没时间了。。。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String line = scanner.nextLine(); int n = Integer.parseInt(line); int[][] area = new int[n][n]; for (int i = 0; i < n; i++) { line = scanner.nextLine(); String[] split = line.split(","); if (split.length != n) { throw new IllegalArgumentException("错误输入"); } int j = 0; for (String num : split) { area[i][j++] = Integer.parseInt(num); } } int minimumTimeCost = getMinimumTimeCost(n, area); System.out.println(minimumTimeCost); } private static int getMinimumTimeCost(int n, int[][] area) { int res = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int t = dfs(area, 0, i, n, 0); // System.out.println("res:" + t); if (t < res && t != -1) res = t; } return res; } static int dfs(int[][] area, int i, int j, int n, int t) { // System.out.println(i + " " + j); if (i > n || j >= n) return -1; if (i == n) return t; if (j == n - 1) return dfs(area, i += 2, j, n, t += area[i - 1][j]); if (area[i + 1][j] <= area[i][j + 1]) return dfs(area, i += 2, j, n, t += area[i - 1][j]); return dfs(area, i, j += 2, n, t += area[i][j - 1]); } }

头脑风暴冷静了一会儿，我猜是不是他一开始可以不走第一行走第二行……