CODEWITHSUNDEEP
javaalgorithmsearchdynamic-programming
Cheesehead
Cheesehead

Reputation: 21

Dynamic Programming Problem: Minimizing A Path Through Array

I'm working on a problem right now where we are provided with a 1D array of values, and must find the path from the first index to the last index that sums to the smallest sum. The only restrictions are that if you go forward, the distance you go must be 1 more than the last "jump", while if you go backwards, you must go the same distance as the last "jump". For instance, given an array int[] values = new int[]{4, 10, 30, 1, 6}, you need to find the path that gets you from position 0 (4) to position 4 (6) that sums up to the smallest amount. The starting indice is not counted, thus, if I go from values[0] to values[1] (which is the only possible starting move), my running total at that point would be 10. From there, I either have the choice to "jump" back the same distance (to values[0]), or "jump" one distance longer than my last jump, which would then be 1+1=2, so jump from values[1] to values[3].

I'm really new to dynamic programming and attempted a solution that went something like this

    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;
    }

However, I recognize that I'm not actually making use of a dynamic programming table here, but I'm not exactly sure what I would store inside that I need to "remember" across calculations, or how I could even utilize it in calculations. From what I see, it appears that I basically have to make a recursive function that evaluates all possible jump distances from an index, store them, and then traverse through the DP table to find the smallest amount? Should I be starting from the last index or the first index of the array to limit possible moves? I watched this video here, and understood the premise, but it seems much more applicable to his 2D Array than anything I have. Any amount of guidance here would be greatly appreciated.

Upvotes: 2

Views: 870

Answers (1)

risingStark
risingStark

Reputation: 1155

In my opinion, this is a 2D DP problem.

dp(i, j) represents the minimum sum required to reach last index from index i and minimum jump allowed of size j.
Let's say you are at index i in the array. Then you can either go to index i-j+1 or index i+j.

So,

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);
}

Time and space complexity O(n * n).

Edit:
Initial function call is recur(values, 0, 1).

I know that the tag of this question is java but I do competitive programming in c++ only. Here I have full working code if you want in c++.

Upvotes: 1

Related Questions