Count of different ways to express N as the sum of 1, 3

Question

What is the logical way to approach this problem ? I found the solution here : solution which looks simple to code but I am having some difficulty understanding it logically.

From the same blog I am not able to understand this line,

So the number that ends with 1 is equal to DP[n-1].

Is there an easier way in which this solution can be explained?

Answer 1

Assume you are going to express 10 as the sum of 1 and 3.Then you can express 10 as 9+1 or 7+3. Then number of different ways that 10 can be expressed is equal to sum of number of different ways that 9 and 7 can be expressed.

i.edp[10]=dp[9]+dp[7]

Answer 2

Just you need to think recursively. Suppose R(n) shows the number of ways to write n as the sum of 1 and 3s. The last number could be 1 or 3. If the last number is 1, we should count R(n-1), and if the last number is 3 we should count R(n-3). We know that the solution of these approach has not any overlap. Because the end number of each o them is different (one of them is 1 and the other one is 3). Therfore, R(n) = R(n-1) + R(n-3).

In addition, to compute R(n), we need three initial values. R(1) = 1, R(2) = 1, and R(3) = 2.