关于分配，动态规划。让我的代码更有效率？

Question

我有一个关于动态规划的作业。我要设计一个执行以下操作的高效算法：有一条小路，布满斑点。用户可以使用一系列按钮向前移动到路径的末端。有3个按钮。一个让你前进 2 个位置，一个让你前进 3 个位置，一个让你前进 5 个位置。路径上的点不是黑就是白，你不能降落在黑点上。该算法找到到达终点所需的最少按钮按下次数（超过最后一个点，可以超过它）。用户输入 "n"，点数。并用 n 个 B 或 W（黑色或白色）填充数组。第一个点必须是白色的。这是我到目前为止所拥有的（它只是伪造的）：

int x = 0
int totalsteps = 0
n = user input
int countAtIndex[n-1] <- Set all values to -1 // I'll do the nitty gritty stuff like this after 
int spots[n-1] = user input

pressButton(totalSteps, x) {
    if(countAtIndex[x] != -1 AND totalsteps >= countAtIndex[x]) {
        FAILED } //Test to see if the value has already been modified (not -1 or not better)
    else
        if (spots[x] = "B") {
            countAtIndex[x] = -2 // Indicator of invalid spot
            FAILED }
        else if (x >= n-5) { // Reached within 5 of the end, press 5 so take a step and win
                GIVE VALUE OF TOTALSTEPS + 1 A SUCCESSFUL SHORTEST OUTPUT 
                FINISH }
        else
            countAtIndex[x] = totalsteps
            pressButton(totalsteps + 1, x+5) //take 5 steps
            pressButton(totalsteps + 1, x+3) //take 3 steps
            pressButton(totalsteps + 1, x+2) //take 2 steps
}

我很欣赏这可能看起来很糟糕，但我希望它没问题，我只是想在我把它写得更好之前确保理论是正确的。我想知道这是否不是解决此问题的最有效方法。除此之外，在有大写字母的地方，我不确定如何 "Fail" 程序，或者如何 return "Successful" 值。任何帮助将不胜感激。

我应该补充一下，以防它不清楚，我正在使用 countAtIndex[] 来存储到达路径中该索引的移动次数。即在位置 3 (countAtIndex[2]) 可能有一个值 1，这意味着它需要 1 次移动才能到达那里。

Answer 1

我正在将我的评论转换为答案，因为这对评论来说太长了。

解决动态规划问题总是有两种方法：自上而下的记忆，或自下而上的系统填充输出数组。我的直觉告诉我，自下而上方法的实施会更简单。我对这个答案的意图是提供该方法的示例。我将把它留作 reader 的练习来编写正式算法，然后实现算法。

举个例子，假设输入数组的前 11 个元素是：

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B  ...

为了解决这个问题，我们创建了一个输出数组（又名 DP table），以保存我们知道的关于这个问题的信息。最初，输出数组中的所有值都设置为无穷大，除了设置为 0 的第一个元素。所以输出数组如下所示：

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - x - x x x - - x -

其中 - 是黑色 space（不允许），并且 x 被用作无穷大的符号（一个无法到达或尚未到达的点尚未达到）。

然后我们从 table 的开头开始迭代，不断更新条目。

从索引0开始，一步到2和5。我们不能移动到 3，因为那个点是黑色的。所以更新后的输出数组如下所示：

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - x 1 x - - x -

接下来，我们跳过索引 1，因为该点是黑色的。所以我们继续索引 2。从 2 开始，我们可以达到 4,5 和 7。索引 4 尚未达到，但现在可以分两步到达。从 2 跳到 5 将在两步内达到 5。但是5已经可以一步到位了，所以我们就不改了（这就是递推关系的用武之地）。我们不能移动到 7，因为它是黑色的。所以在处理索引 2 之后，输出数组如下所示：

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 x - - x -

在跳过索引 3（黑色）和处理索引 4（可以达到 6 和 9）后，我们有：

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 3 - - 3 -

处理索引 5 不会改变任何东西，因为 7、8、10 都是黑色的。索引 6 没有任何改变，因为 8 是黑色的，三步就可以到达 9，我们没有显示索引 11。索引 7 和 8 被跳过，因为它们是黑色的。从 9 开始的所有跳转都进入了未显示的数组部分。

因此，如果目标是到达索引 11，则移动次数为 4，可能的路径为 2,4,6,11 或 2,4,9,11。或者如果数组继续，我们将简单地继续遍历数组，然后检查数组的最后五个元素，看看哪个元素的移动次数最少。

关于分配，动态规划。让我的代码更有效率？

Assignment regarding, dynamic programming. Making my code more efficient?

algorithm

dynamic

pseudocode

memoization