# 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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

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

**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:

DP_{n = DPn-1 + DPn-3 + DPn-4}

Base case :DP[0] = DP[1] = DP[2] = 1 and DP[3] = 2

## C++

`// C++ program to illustrate the number of` `// ways to represent N as sum of 1, 3 and 4.` `#include <bits/stdc++.h>` `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

`<?php` `// PHP 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` `function` `countWays(` `$n` `)` `{` ` ` `$DP` `= ` `array` `();` ` ` `// base cases` ` ` `$DP` `[0] = ` `$DP` `[1] = ` `$DP` `[2] = 1;` ` ` `$DP` `[3] = 2;` ` ` `// iterate for all` ` ` `// values from 4 to n` ` ` `for` `(` `$i` `= 4; ` `$i` `<= ` `$n` `; ` `$i` `++)` ` ` `$DP` `[` `$i` `] = ` `$DP` `[` `$i` `- 1] +` ` ` `$DP` `[` `$i` `- 3] +` ` ` `$DP` `[` `$i` `- 4];` ` ` ` ` `return` `$DP` `[` `$n` `];` `}` `// Driver Code` `$n` `= 10;` `echo` `countWays(` `$n` `);` `// This code is contributed` `// by Sam007` `?>` |

## Javascript

`<script>` `// Javascript 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` `function` `countWays(n)` `{` ` ` `var` `DP = [];` ` ` `DP.length = 10;` ` ` `DP.fill(0);` ` ` `// Base cases` ` ` `DP[0] = DP[1] = DP[2] = 1;` ` ` `DP[3] = 2;` ` ` `// Iterate for all values from 4 to n` ` ` `for` `(` `var` `i = 4; i <= n; i++)` ` ` `DP[i] = DP[i - 1] + DP[i - 3] +` ` ` `DP[i - 4];` ` ` `return` `DP[n];` `}` `// Driver code` `var` `n = 10;` `document.write(countWays(n));` `// This code is contributed by bunnyram19 ` `</script>` |

**Output:**

64

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