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++
// 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>
Producción:
64
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)