今日国内某大厂笔试题解析

输入随机一个3*n的矩阵，从每一列的三个元素中任取，一共取出n个元素，编号b(1)------b(n)

令 res= |b(i+1)-b(i)| 绝对值的累加，1<=i<=n-1; 求res的最小值。

动态规划、递归问题。

先定位第一列，在递归定位再二列、第n列：

<code>import java.util.Scanner;

public class Solution {
    static int len = 0;
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        len = n;
        //输入3*n矩阵
        int array[][] = new int[3][n];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                array[i][j] = s.nextInt();
            }
        }
        //GetPathWeight(array,i,j):获取从array[i][j]为起点的路径长度，
        //再比较三行中最小的PathWeight，输出
        int min_path = Integer.MAX_VALUE, tp;
        for (int i = 0; i < 3; i++) {
            tp = GetPathWeight(array, i, 0);
            if (tp < min_path) min_path = tp;
        }
        System.out.println("res最小值:"+min_path);
    }


    private static int GetPathWeight(int[][] array, int i, int j) {
        if (j == len - 1) return 0;
        int perRes = Integer.MAX_VALUE;
        int tp = 0;
        int pre = 0;
        int outputnumber=0;
        //这里要注意的是pre保存上一层的输出，有点像神经网络
        for (int k = 0; k < 3; k++) {
            pre = Math.abs(array[k][j + 1] - array[i][j]);
            tp = pre + GetPathWeight(array, k, j + 1);
            if (tp < perRes){
                perRes = tp;
            }
        }
        return perRes;
    }
}
/<code>

閱讀更多 海上的煙火9527 的文章

關鍵字: min 中任取 perRes