CODEWITHSUNDEEP
pythonarraysalgorithmdynamic-programming
IReallyNeedAnAnswer
IReallyNeedAnAnswer

Reputation: 23

Dynamic Programming - minimize the sum of the array

My problem is: given an array of negative and positive integers. You are given value j to jump and r to rest. After each jump, you need to rest for r steps. Moreover, you are allowed to move 1 more step forward even when you have the ability to jump. The problem is to minimize the sum of the array.

Ex.1 r = 2, j = 2, [5, 3, -4, -2, 1, 2, 3] => -4 + -2 + 3 = -3 (Jump 5, 3, Rest -4,-2, Jump 1,2, Rest 3)

Ex.2 r = 2, j = 3, [90, 91, 92, -2, 3, 55, 3] => -2 + 3 + 55 + 3 = 59 (Jump 90,91,92 Rest -2,3,55,3)

My Idea: I decided to use DP to solve this. This is my pseudocode.

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 is array used to store best sums.

The problem that it does not work for all inputs, can you help me spot where I am going wrong. Consider the example r = 2, j = 2 , [2 ,-2 ,-3,1 ,3 ,4]. The answer should be 1 (Visit 2, -2, Jump -3, Rest 4) 2-2-3+4 = 1, but my program outputs 5

Upvotes: 2

Views: 755

Answers (1)

Juan Carlos Ramirez
Juan Carlos Ramirez

Reputation: 2129

Your problem seems to be in this line:

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

This prevents you from ever choosing Visit whenever i is 0, since you ALWAYS jump in your first step. I don't know about your full code, but this part should be:

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
                )

Also, your code give you an out-of-bounds error if jump>len(MIN)-1. If this condition is true, you know you should ALWAYS visit. Given all of this, I'm going to write the recursive formula, you can then memoize it:

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

Upvotes: 1

Related Questions