阿里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); //        } //    } }


#阿里巴巴##笔试题目#
全部评论
测试用例是这个,它给的答案是76,跳跃的路径应该是35--65--56--85,跳过的格子是5--1--18--52,加起来76。但是如果在倒数第二行往左跳一格,再往下跳,值会更小。不知道是不是哪里理解错了 8 35   92   98   68   35   65   26   72    29   78   83   16   5   89   92   28    48   51   37   79   65   74   50   71    98   78   99   57   1   30   22   16    72   88   55   33   56   58   28   49    4   28   29   20   18   61   11   73    61   19   47   34   85   32   77   89    29   49   10   81   52   5   63   25
点赞 回复 分享
发布于 2019-08-30 21:18
请教一下,为啥n=8那个测试用例的结果是76呀,笔算能找到更小的解
点赞 回复 分享
发布于 2019-08-30 21:08
回溯法。。40  调了好久,第二题直接没看。。
点赞 回复 分享
发布于 2019-08-30 21:06
牛客上看了那么多还是没有人A的,也许这是一个压力测试,故意把最好结果设为40%,考验大家的时间管理能力,抗压能力吧。
点赞 回复 分享
发布于 2019-08-30 21:05
同。。二维动态规划只有40
点赞 回复 分享
发布于 2019-08-30 20:57

相关推荐

不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
评论
1
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务