动态规划最小化数组和

Question

我的问题是：给定一个正负整数数组。给你值j跳，r停。每次跳跃后，你都需要休息r步。此外，即使你有跳跃的能力，你也可以再向前走一步。问题是最小化数组的和。你知道吗

例1 r = 2, j = 2, [5, 3, -4, -2, 1, 2, 3]=>；-4+-2+3=-3（跳跃5，3，休息-4，-2，跳跃1，2，休息3）

例2 r = 2, j = 3, [90, 91, 92, -2, 3, 55, 3]=>；-2+3+55+3=59（跳跃90,91,92休息-2,3,55,3）

---

我的想法是：我决定用DP来解决这个问题。这是我的伪代码。你知道吗

def minimalSum (MIN, array, jump, rest, steps_left_to_jump, i):
    if MIN[i] is not empty:
        return MIN[i]
    if i == len(array) - 1:
        MIN[i] = array[i]
    else:
        if steps_left_to_jump == 0:
            if i == 0:
                MIN[i] = minimalSum(MIN, array, jump, rest, rest - 1, jump)
            else:
                if i + jump + 1 < len(array):
                    MIN[i] = array[i] + minimalSum(MIN, array, jump, rest, rest - 1, i + jump + 1)
            o1 = array[i] + minimalSum(MIN, array, jump, rest, 0, i + 1)
            if MIN[i] is not None:
                if o1 < MIN[i]:
                    MIN[i] = o1
            else:
                MIN[i] = o1
        else:
            MIN[i] = array[i] + minimalSum(MIN, array, jump, rest, steps_left_to_jump - 1, i + 1)
    return MIN[i]

MIN是用于存储最佳和的数组。你知道吗

问题是，它不适用于所有的输入，你能帮我找出哪里我做错了。考虑一下这个例子 r = 2, j = 2 , [2 ,-2 ,-3,1 ,3 ,4]。答案应该是1（访问2，-2，跳跃-3，休息4）2-2-3+4=1，但我的程序输出5

Answer 1

你的问题似乎在这一行：

if i == 0:
    MIN[i] = minimalSum(MIN, array, jump, rest, rest - 1, jump)

这会阻止你在我为0时选择访问，因为你总是在第一步就跳。我不知道你的完整代码，但这部分应该是：

if i == 0:
    MIN[i] = min(minimalSum(MIN, array, jump, rest, rest - 1, jump) , # case where you jump at 0
                 array[0] + minimalSum(MIN, array, jump, rest, 0, 1)  # case where you visit index 0
                )

另外，如果jump>len(MIN)-1，代码会给您一个越界错误。如果这种情况是真的，你知道你应该经常去看医生。 考虑到所有这些，我要写一个递归公式，你可以把它记忆起来：

def opt_sum(array, r, j):
    if j > len(array)-1:
        return sum(array)  # cannot jump, return sum of full array
    else:
        visit_val = array[0] + opt_sum(array[1:], r, j)  # best sum if you choose to visit index 0
        jump_val = (
                sum(array[j:j+r])     # total mandatory resting visits
                + opt_sum(array[j+r:], r, j)  # the optimal sum of the subarray
                )                             # starting after the rest
        return min(visit_val, jump_val)  # return best of both policies