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