Cuente las diferentes formas de expresar N como la suma de 1, 3 y 4

Dado N, cuente el número de formas de expresar N como la suma de 1, 3 y 4.

Ejemplos: 

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

Planteamiento: Divida el problema en subproblemas para resolverlo. Sea DP[n] el número de formas de escribir N como la suma de 1, 3 y 4. Considere una solución posible con n = x1 + x2 + x3 + … xn. Si el último número es 1, entonces la suma de los números restantes es n-1. Entonces el número que termina en 1 es igual a DP[n-1]. Teniendo en cuenta otros casos donde el último número es 3 y 4. La recurrencia final sería: 

DPn = DPn-1 + DPn-3 + DPn-4

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

// 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 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.

# 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# 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 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
?>

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

Producción: 

64

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)