时间戳

首页 > 解决方案 > 动态规划问题：最小化通过数组的路径

java - 动态规划问题：最小化通过数组的路径

问题描述

我现在正在处理一个问题，我们提供了一个一维数组值，并且必须找到从第一个索引到最后一个索引的路径，该路径总和为最小和。唯一的限制是，如果你向前走，你走的距离必须比上一次“跳跃”多1，而如果你向后走，你必须走和最后一次“跳跃”相同的距离。例如，给定一个数组int[] values = new int[]{4, 10, 30, 1, 6}，您需要找到从位置 0 (4) 到位置 4 (6) 的路径，该路径的总和最小。起始指数不计算在内，因此，如果我从values[0]到values[1]（这是唯一可能的起始移动），我在该点的运行总数将为 10。从那里，我可以选择“跳”回相同的距离（至values[0])，或者“跳”比我上次跳跃的距离长一个距离，这将是 1+1=2，所以从values[1]跳到values[3]。

我对动态编程真的很陌生，并尝试了一个类似这样的解决方案

    public static int smallestCalc(int[] values, int prevJump, int pos, int runTot) {
        while (pos != penal.length) {
            int forwards = 600;
            int backwards = 600;
            try {
                backwards = penal[pos - prevJump];
            } catch (Exception ignore) {}
            try {
                forwards = penal[pos + prevJump+1];
            } catch (Exception ignore) {}
            int min = Math.min(forwards,backwards);
            if (min == backwards) {
                pos -= prevJump;
            } else {
                pos += prevJump + 1;
                prevJump ++;
            }
            runTot+=min;
            smallestCalc(values, prevJump, pos, runTot);
        }
        return runTot;
    }

但是，我认识到我实际上并没有在这里使用动态编程表，但我不确定我会在里面存储什么我需要在计算中“记住”，或者我什至如何在计算中使用它. 从我所见，看来我基本上必须创建一个递归函数来评估索引中所有可能的跳跃距离，存储它们，然后遍历 DP 表以找到最小的量？我应该从数组的最后一个索引还是第一个索引开始以限制可能的移动？我在这里观看了这个视频，并理解了这个前提，但它似乎比我所拥有的任何东西都更适用于他的 2D 阵列。任何数量的指导将不胜感激。

标签： javaalgorithmsearchdynamic-programming

解决方案

在我看来，这是一个 2D DP 问题。

dp(i, j) 表示从索引 i 到达最后一个索引所需的最小总和以及大小 j 允许的最小跳转。
假设您位于数组中的索引 i 处。然后您可以转到索引 i-j+1 或索引 i+j。

所以，

int recur(int values[], int i, int j){
    // base case. Here n is size of values array
    if(i==n-1)
        return 0;
    
    if(dp[i][j] != -1){
    /* here -1 is taken as to mark never calculated state of dp. 
    If the values[] array also contains negative values then you need to change it to 
    something appropriate.
    */
        return dp[i][j];
    }
    int a = INT_MAX;
    int b = a;
    if(i>0 && (i-j+1)>=0)
        a = values[i-j + 1] + recur(values, i-j+1, j);
    if(i+j < n)
        b = values[i+j] + recur(values, i+j, j+1);
    return dp[i][j] = min(a, b);
}

时间和空间复杂度 O(n * n)。

编辑：
初始函数调用是recur(values, 0, 1).

我知道这个问题的标签是 java，但我只用 c++ 进行竞争性编程。如果你想在 C++ 中使用，我在这里有完整的工作代码。

推荐阅读