[数据结构与算法]阿里0325笔试第一题（动态规划）

1：题目描述

链接：https://www.nowcoder.com/discuss/391530?type=1
来源：牛客网

第一题，给定一个数组n，比如
5 10 5 4 4
1 7 8 4 0
3 4 9 0 3
从每一列选择一个数，求出后一列减去前一列的绝对值的和的最小值
比如这里就是3 4 5 4 4，所以输出是3

2：解题思路

• 本地我们经过分析，可以明确发现本列最短路径和上一列最短路径之间有很大的关系，我们可以使用动态规划的思想解决这个问题，我们简化问题，以arr[3][n]数组举例：

• 从第一列开始，每次寻找到达该列每一行的最短路径，最终求出到达最后一列每一行的最短路径，取到达最后一列每一行的最短路径的最小值，即为最后的结果。

• 例如：设数组第一行的值为a0,a1,a2，数组第二行的值为b0,b1,b2，到达第一列每一行的最短路径为int[] dp = {0,0,0},到达第二列每一行的最短路径为：
  第二列第一行：next[0] = min(dp[0] + abs(a0-b0),dp[1] + abs(a1-b0),dp[2] + abs(a2-b0))
  第二列第二行：next[1] = min(dp[0] + abs(a0-b1),dp[1] + abs(a1-b1),dp[2] + abs(a2-b1))
  第二列第三行：next[2] = min(dp[0] + abs(a0-b2),dp[1] + abs(a1-b2),dp[2] + abs(a2-b2))

• 依次推出第i列的每一行的最短路径为：
  第i列第一行：next[0] = min(abs(arr[0][i] - arr[0][i - 1]) + dp[0],abs(arr[0][i] - arr[1][i - 1]) + dp[1]),abs(arr[0][i] - arr[2][i - 1]) + dp[2])
  第i列第二行：next[1] = min(abs(arr[1][i] - arr[0][i - 1]) + dp[0],abs(arr[1][i] - arr[1][i - 1]) + dp[1]),abs(arr[1][i] - arr[2][i - 1]) + dp[2])
  第i列第三行：next[2] = min(abs(arr[2][i] - arr[0][i - 1]) + dp[0],abs(arr[2][i] - arr[1][i - 1]) + dp[1]),abs(arr[2][i] - arr[2][i - 1]) + dp[2])

• 每次求出当前列的最短路径，将next[]赋值给dp[]，以便进行下面的循环。

• 当求出第n列的每一行的最短路径时，取其中的最小值作为最终的结果，minDistance = min(dp[0],dp[1],dp[2])

3：代码示例

import java.util.Scanner;

/**
 * @author  xrw
 * @date 2021/8/8
 * 阿里0325笔试
 * 第一题，给定一个数组n，比如
 * 5  0  5  4  4
 * 1  7  8  4  0
 * 3  4  9  0  3
 * 从每一列选择一个数，求出后一列减去前一列的绝对值的和的最小值
 */
public class Main{
    static int n ;//数组的列数
    static int[][] arr;//二维数组
    static int[] dp;//到达当前列的前一列的最短路径
    static int[] next;//到达当前列的最短路径
    static int minDistance;//最短路径
    //1 2 3 4 5
    //2 3 4 5 6
    //23 45 12 5 2
    //结果为3
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        if (n<=1){//少于2行，此题无意义
            return;
        }
        arr = new int[3][n];
        for (int i = 0; i < 3; i++) {//从键盘创建一个数组
            for (int j = 0; j < n; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < 3; i++) {//遍历显示数组
            for (int j = 0; j < n; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println("");
        }
        dp = new int[]{0, 0, 0};//初始化
        next = new int[]{0, 0, 0};//初始化
        minDistance = 0;//初始化
        minDistance = getMinDitance(arr);//求最短路径
        System.out.println(minDistance);
    }

    public static int getMinDitance(int[][] arr) {
        for (int i = 1; i < n; i++) {//外围循环控制列数
            for (int j = 0; j < 3; j++) {//内围循环控制行数
                next[j] = Math.min(Math.min(Math.abs(arr[j][i] - arr[0][i - 1]) + dp[0],
                        Math.abs(arr[j][i] - arr[1][i - 1]) + dp[1]),
                        Math.abs(arr[j][i] - arr[2][i - 1]) + dp[2]);
            }
            for (int k = 0; k < 3; k++) {//讲本行的值作为上一行的值，以便求到达下一行的最短路径
                dp[k] = next[k];
            }
        }

        return Math.min(Math.min(dp[0], dp[1]), dp[2]);
    }
}