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
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!!
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:
You had the number n-1, you added 1 to it to get n.
You had the number n-3, you added 3 to it to get n.
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)