阿里30号笔试兔子跳那题
阿里笔试题,兔子跳那题,有人A了吗?我O(n^2)只能过40%
题目如下。
给出一个边长为n (6<=n<=30) 的正方形矩阵。从第一行的任意位置出发,每次只能往右跳两格或者往下跳两格。每一步经过的长度是 两个落点之间的元素的大小。求最短路径长度。
比如
n=6
1 | 2 | 3 | 4 | 5 | 6 |
7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 |
31 | 32 | 33 | 34 | 35 | 36 |
假如输入矩阵如上图,最短路径就是从 1 -> 13 -> 25 ->
长度就是 7+19+31
这是我的理解,可能就错在理解吧。
下面是我代码。求大神指教
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[][] step=new int[area.length][area.length]; for(int j=0;j<n;j++){ step[2][j]=area[1][j]; } for(int i=4;i<n;i+=2){ for(int j=0;j<n;j++){ step[i][j]=step[i-2][j]+area[i-1][j]; if(j>=2) step[i][j]=Math.min(step[i][j],step[i][j-2]+area[i][j-1]); } } int minRs=Integer.MAX_VALUE; if(n%2==0){ for(int j=0;j<n;j++) minRs=Math.min(step[n-2][j]+area[n-1][j],minRs); return minRs; }else{ for(int j=0;j<n;j++) minRs=Math.min(step[n-1][j],minRs); return minRs; } } // private static void helper(int i,int j,int length,int[][] area){ // if(length>minRs) return; // if( j>=area.length) return; // if(i==0) // helper(2,j,area[1][j],area); // else if(i>=area.length-1) // minRs=Math.min(minRs,length); // else{ // helper(i+2,j,area[i+1][j]+length,area); // // if(j+2<area.length) // helper(i,j+2,length+area[i][j+1],area); // } // } }