Can anyone explain this simple DP problem?

Problem: given n, find the number of different ways to write
n as the sum of 1, 3, 4

Sub-problem: DPn be the number of ways to write N as the sum of 1, 3, and 4.
Finding recurrence: Consider one possible solution, n = x1 + x2 + … xn. If the last number is 1, the sum of the remaining numbers should be n - 1. So, number of sums that end with 1 is equal to DPn-1… Take other cases into account where the last number is 3 and 4. The final recurrence would be:

DPn = DPn-1 + DPn-3 + DPn-4.

Take care of the base cases. DP0 = DP1 = DP2 = 1, and DP3 = 2.

I dont understand how base cases can be 1? and it’d help if someone could explain the recurrence relation as well

1 Like

Lets say ,dp[n] is the number of ways n can be expressed as sum of 1,3 and 4
Now
n = 1 + (n-1)
n = 3 + (n-3)
n = 4 +(n-4)
If u can achieve sum n-1 in dp[n-1] ways then adding 1 to all of them gives dp[n-1] ways to make n as sum, similarly for 3 and 4
we have dp[n] = dp[n-1]+dp[n-3]+dp[n-4]

For base cases :
dp[0] = number of ways 0 can be achieved using 1,3,4 = 0
dp[1] = 1 {1}
dp[2] = 1 { 1+1 }
dp[3] = 2 { 3 , 1+1+1 }
Peace!!

1 Like

If you got the approach and looking for solution , here is how you can get it .

for(int i=4;i<=n;i++)
{
// use the above recurrence relation here
}

return dp[n];

Correct me if i’m wrong.

You added a few numbers you ended up with the number n. Lets take that for granted. This was your final state, right?

But what about the state just before you attained this number n? There are three possibilities:

  1. You had the number n-1, you added 1 to it to get n.
  2. You had the number n-3, you added 3 to it to get n.
  3. You had the number n-4, you added 4 to it to get n.

Thus DP(n) is sum of DP(n-1)+DP(n-3)+DP(n-4).

Now that we have established recurrence, lets find out the base cases.
a. if(n < 0) DP[n] = 0 since there is no way to obtain a negative with 1,3,4
b. if(n ==0) exactly one way in which we can obtain this, that is by using no numbers.
c. If(n==1) DP[n] = 1 since there is EXACTLY one way to obtain 1 with 1,3,4.
d. If(n==2) DP[n] = 1 since there is EXACTLY one way to obtain 2 with 1,3,4 - using both 1s.
e. If(n==3) DP[n] = 2 since we can obtain it with 3 or 1+1+1 (check this with our formula too)
f. if(n==4) DP[n] = 3 since we can obtain it with 4 or 3+1 or 1+1+1+1 (check this with our formula too)

Having established all the above

we can simply do this to get the full DP.

vector<int> DP(n+1,0);
DP[0] = 1,     DP[1] = 1,     DP[2] = 1;     
DP[3] = 2;     DP[4] = 3;
for(auto i = 5; i <=n; i++)
{
    DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
}

Thanks, got it!

The initial conditions can be expressed even more compactly:

  • DP(0) = 1 (there’s only one way to make zero - add no numbers)
  • DP(x<0) = 0 (there’s no way to make negative numbers)

Then the other given cases come out of the recurrence:

  • DP(1) = DP(0) + DP(-2) + DP(-3) = 1 + 0 + 0 = 1
  • DP(2) = DP(1) + DP(-1) + DP(-2) = 1 + 0 + 0 = 1
  • DP(3) = DP(2) + DP(0) + DP(-1) = 1 + 1 + 0 = 2