动态规划问题:最小化通过阵列的路径

Question

我现在正在处理一个问题，我们得到了一个1D值数组，并且必须找到从第一个索引到最后一个索引的路径，该路径的总和为最小和。唯一的限制是，如果你向前走，你所走的距离必须比最后一个"距离"多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阵列。如能提供任何指导，我们将不胜感激。

Answer 1

在我看来，这是一个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++中使用，这里我有完整的工作代码。