CODEWITHSUNDEEP
javadynamic-programming
unsaturatedgoods1
unsaturatedgoods1

Reputation: 33

Leetcode #377 Dynamic Programming Logic Question

I have been struggling to comprehend one of the discussion solutions shown from LC #377. I'm not grasping how result is being incremented. I can see that there is the line:

result += combinations(nums, dp, target - nums[i])

which obviously is incrementing result, but how exactly is result being incremented? All I can see that is result is initialized to 0 then the line is executed if that if condition is satisfied, so wouldn't the line:

dp[target] = result

always be set to 0?. Really struggling comprehending, so would appreciate any help.

Code:

class Solution {
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, -1);
    dp[0] = 1;
    return combinations(nums, dp, target);
}

public int combinations(int[] nums, int[] dp, int target) {
    if (dp[target] != -1) {
        return dp[target];
    }
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            result += combinations(nums, dp, target - nums[i]);
        }
    }
    dp[target] = result;
    return result;
}

}

Upvotes: 0

Views: 65

Answers (1)

Jagrut Sharma
Jagrut Sharma

Reputation: 4754

Focusing reply on your question around result being incremented. This is the code you mentioned:

    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            result += combinations(nums, dp, target - nums[i]);
        }
    }
    dp[target] = result;

There is a for loop that increments i from 0 to nums.length-1. For each such i, if this condition is met (target >= nums[i]), then result is updated by each call to combinations(nums, dp, target - nums[i]). You can see from the signature that combinations() returns an int value.

When dp[target] = result is reached, the result has sum of the values returned by each of the calls to combinations().

The following code may help you. It counts the total even numbers between 1 to n. I wrote it to match the flavor of recursion used in your post. Hope it helps.

public class SumDemo {
    int checkEven(int n) {
        return (n % 2 == 0) ? 1 : 0;
    }

    int countEven(int n) {
        int result = 0;
        for (int i = 1; i <=n; i++) {
            result += checkEven(i);
        }
        return result;
    }

    public static void main(String[] args) {
        SumDemo demo = new SumDemo();
        System.out.println(demo.countEven(10));
    }
}

Result:
5

(Since there are 5 even numbers between 1 to 10 (both inclusive)): 2, 4, 6, 8, 10

Upvotes: 1

Related Questions