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

Given N, count the number of ways to express N as sum of 1, 3 and 4.

Examples:

```Input :  N = 4
Output : 4
Explanation: 1+1+1+1
1+3
3+1
4

Input : N = 5
Output : 6
Explanation: 1 + 1 + 1 + 1 + 1
1 + 4
4 + 1
1 + 1 + 3
1 + 3 + 1
3 + 1 + 1
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach : Divide the problem into sub-problems for solving it. Let DP[n] be the be the number of ways to write N as the sum of 1, 3, and 4. Consider one possible solution with n = x1 + x2 + x3 + … xn. If the last number is 1, then sum of the remaining numbers is n-1. So the number that ends with 1 is equal to DP[n-1]. Taking other cases into account where the last number is 3 and 4. The final recurrence would be:

```DPn = DPn-1 + DPn-3 + DPn-4
```
```Base case :
DP[0] = DP[1] = DP[2] = 1 and DP[3] = 2
```

## C++

 `// CPP program to illustrate the number of ` `// ways to represent N as sum of 1, 3 and 4. ` `#include ` `using` `namespace` `std; ` ` `  `// function to count the number of ` `// ways to represent n as sum of 1, 3 and 4 ` `int` `countWays(``int` `n) ` `{ ` `    ``int` `DP[n + 1]; ` ` `  `    ``// base cases ` `    ``DP[0] = DP[1] = DP[2] = 1; ` `    ``DP[3] = 2; ` ` `  `    ``// iterate for all values from 4 to n ` `    ``for` `(``int` `i = 4; i <= n; i++)  ` `        ``DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]; ` `     `  `    ``return` `DP[n]; ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``int` `n = 10; ` `    ``cout << countWays(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to illustrate  ` `// the number of ways to represent  ` `// N as sum of 1, 3 and 4. ` ` `  `class` `GFG { ` ` `  `    ``// Function to count the  ` `    ``// number of ways to represent  ` `    ``// n as sum of 1, 3 and 4 ` `    ``static` `int` `countWays(``int` `n) ` `    ``{ ` `        ``int` `DP[] = ``new` `int``[n + ``1``]; ` ` `  `        ``// base cases ` `        ``DP[``0``] = DP[``1``] = DP[``2``] = ``1``; ` `        ``DP[``3``] = ``2``; ` ` `  `        ``// iterate for all values from 4 to n ` `        ``for` `(``int` `i = ``4``; i <= n; i++) ` `            ``DP[i] = DP[i - ``1``] + DP[i - ``3``]  ` `                    ``+ DP[i - ``4``]; ` ` `  `        ``return` `DP[n]; ` `    ``} ` ` `  `    ``// driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `n = ``10``; ` `        ``System.out.println(countWays(n)); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by prerna saini. `

## Python3

 `# Python program to illustrate the number of ` `# ways to represent N as sum of 1, 3 and 4. ` ` `  `# Function to count the number of ` `# ways to represent n as sum of 1, 3 and 4 ` `def` `countWays(n): ` ` `  `    ``DP ``=` `[``0` `for` `i ``in` `range``(``0``, n ``+` `1``)] ` `     `  `    ``# base cases ` `    ``DP[``0``] ``=` `DP[``1``] ``=` `DP[``2``] ``=` `1` `    ``DP[``3``] ``=` `2` ` `  `    ``# Iterate for all values from 4 to n ` `    ``for` `i ``in` `range``(``4``, n ``+` `1``): ` `        ``DP[i] ``=` `DP[i ``-` `1``] ``+` `DP[i ``-` `3``] ``+` `DP[i ``-` `4``] ` `     `  `    ``return` `DP[n] ` ` `  `     `  `# Driver code  ` `n ``=` `10` `print` `(countWays(n)) ` ` `  `# This code is contributed by Gitanjali. `

## C#

 `// C# program to illustrate  ` `// the number of ways to represent  ` `// N as sum of 1, 3 and 4. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function to count the  ` `    ``// number of ways to represent  ` `    ``// n as sum of 1, 3 and 4 ` `    ``static` `int` `countWays(``int` `n) ` `    ``{ ` `        ``int` `[]DP = ``new` `int``[n + 1]; ` ` `  `        ``// base cases ` `        ``DP[0] = DP[1] = DP[2] = 1; ` `        ``DP[3] = 2; ` ` `  `        ``// iterate for all values from 4 to n ` `        ``for` `(``int` `i = 4; i <= n; i++) ` `            ``DP[i] = DP[i - 1] + DP[i - 3]  ` `                    ``+ DP[i - 4]; ` ` `  `        ``return` `DP[n]; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 10; ` `        ``Console.WriteLine(countWays(n)); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by vt_m. `

## PHP

 ` `

Output:

```64
```

Time Complexity : O(n)
Auxiliary Space : O(n)