Dados dos números naturales n y m . La tarea es encontrar el número de formas en que los números que son mayores o iguales que m se pueden sumar para obtener la suma n.
Ejemplos:
Input : n = 3, m = 1 Output : 3 Following are three different ways to get sum n such that each term is greater than or equal to m 1 + 1 + 1, 1 + 2, 3 Input : n = 2, m = 1 Output : 2 Two ways are 1 + 1 and 2
La idea es usar Programación Dinámica definiendo una array 2D, digamos dp[][]. dp[i][j] define el número de formas de obtener la suma i usando los números mayores o iguales que j. Entonces dp[i][j] se puede definir como:
Si i < j, dp[i][j] = 0 , porque no podemos lograr una suma menor de i usando números mayores o iguales que j.
Si i = j, dp[i][j] = 1 , porque solo hay una forma de mostrar la suma i usando el número i que es igual a j.
De lo contrario, dp[i][j] = dp[i][j+1] + dp[ij][j] , porque obtener una suma i usando números mayores o iguales que j es igual a la suma de obtener una suma de i usando números mayores o iguales a j+1 y obteniendo la suma de ij usando números mayores o iguales a j.
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find number of ways to
// which numbers that are greater than
// given number can be added to get sum.
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
// Return number of ways to which numbers
// that are greater than given number can
// be added to get sum.
int numberofways(int n, int m)
{
int dp[n+2][n+2];
memset(dp, 0, sizeof(dp));
dp[0][n + 1] = 1;
// Filling the table. k is for numbers
// greater than or equal that are allowed.
for (int k = n; k >= m; k--) {
// i is for sum
for (int i = 0; i <= n; i++) {
// initializing dp[i][k] to number
// ways to get sum using numbers
// greater than or equal k+1
dp[i][k] = dp[i][k + 1];
// if i > k
if (i - k >= 0)
dp[i][k] = (dp[i][k] + dp[i - k][k]);
}
}
return dp[n][m];
}
// Driver Program
int main()
{
int n = 3, m = 1;
cout << numberofways(n, m) << endl;
return 0;
}
Java
// Java Program to find number of ways to
// which numbers that are greater than
// given number can be added to get sum.
import java.io.*;
class GFG {
// Return number of ways to which numbers
// that are greater than given number can
// be added to get sum.
static int numberofways(int n, int m)
{
int dp[][]=new int[n+2][n+2];
dp[0][n + 1] = 1;
// Filling the table. k is for numbers
// greater than or equal that are allowed.
for (int k = n; k >= m; k--) {
// i is for sum
for (int i = 0; i <= n; i++) {
// initializing dp[i][k] to number
// ways to get sum using numbers
// greater than or equal k+1
dp[i][k] = dp[i][k + 1];
// if i > k
if (i - k >= 0)
dp[i][k] = (dp[i][k] + dp[i - k][k]);
}
}
return dp[n][m];
}
// Driver Program
public static void main(String args[])
{
int n = 3, m = 1;
System.out.println(numberofways(n, m));
}
}
/*This code is contributed by Nikita tiwari.*/
Python3
# Python3 Program to find number of ways to # which numbers that are greater than # given number can be added to get sum. MAX = 100 import numpy as np # Return number of ways to which numbers # that are greater than given number can # be added to get sum. def numberofways(n, m) : dp = np.zeros((n + 2, n + 2)) dp[0][n + 1] = 1 # Filling the table. k is for numbers # greater than or equal that are allowed. for k in range(n, m - 1, -1) : # i is for sum for i in range(n + 1) : # initializing dp[i][k] to number # ways to get sum using numbers # greater than or equal k+1 dp[i][k] = dp[i][k + 1] # if i > k if (i - k >= 0) : dp[i][k] = (dp[i][k] + dp[i - k][k]) return dp[n][m] # Driver Code if __name__ == "__main__" : n, m = 3, 1 print(numberofways(n, m)) # This code is contributed by Ryuga
C#
// C# program to find number of ways to
// which numbers that are greater than
// given number can be added to get sum.
using System;
class GFG {
// Return number of ways to which numbers
// that are greater than given number can
// be added to get sum.
static int numberofways(int n, int m)
{
int[, ] dp = new int[n + 2, n + 2];
dp[0, n + 1] = 1;
// Filling the table. k is for numbers
// greater than or equal that are allowed.
for (int k = n; k >= m; k--) {
// i is for sum
for (int i = 0; i <= n; i++) {
// initializing dp[i][k] to number
// ways to get sum using numbers
// greater than or equal k+1
dp[i, k] = dp[i, k + 1];
// if i > k
if (i - k >= 0)
dp[i, k] = (dp[i, k] + dp[i - k, k]);
}
}
return dp[n, m];
}
// Driver Program
public static void Main()
{
int n = 3, m = 1;
Console.WriteLine(numberofways(n, m));
}
}
/*This code is contributed by vt_m.*/
PHP
<?php
// PHP Program to find number of ways to
// which numbers that are greater than
// given number can be added to get sum.
$MAX = 100;
// Return number of ways to which numbers
// that are greater than given number can
// be added to get sum.
function numberofways($n, $m)
{
global $MAX;
$dp = array_fill(0, $n + 2, array_fill(0, $n+2, NULL));
$dp[0][$n + 1] = 1;
// Filling the table. k is for numbers
// greater than or equal that are allowed.
for ($k = $n; $k >= $m; $k--)
{
// i is for sum
for ($i = 0; $i <= $n; $i++)
{
// initializing dp[i][k] to number
// ways to get sum using numbers
// greater than or equal k+1
$dp[$i][$k] = $dp[$i][$k + 1];
// if i > k
if ($i - $k >= 0)
$dp[$i][$k] = ($dp[$i][$k] + $dp[$i - $k][$k]);
}
}
return $dp[$n][$m];
}
// Driver Program
$n = 3;
$m = 1;
echo numberofways($n, $m) ;
return 0;
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript Program to find number of ways to
// which numbers that are greater than
// given number can be added to get sum.
// Return number of ways to which numbers
// that are greater than given number can
// be added to get sum.
function numberofways(n,m)
{
let dp=new Array(n+2);
for(let i=0;i<dp.length;i++)
{
dp[i]=new Array(n+2);
for(let j=0;j<dp[i].length;j++)
{
dp[i][j]=0;
}
}
dp[0][n + 1] = 1;
// Filling the table. k is for numbers
// greater than or equal that are allowed.
for (let k = n; k >= m; k--) {
// i is for sum
for (let i = 0; i <= n; i++) {
// initializing dp[i][k] to number
// ways to get sum using numbers
// greater than or equal k+1
dp[i][k] = dp[i][k + 1];
// if i > k
if (i - k >= 0)
dp[i][k] = (dp[i][k] + dp[i - k][k]);
}
}
return dp[n][m];
}
// Driver Program
let n = 3, m = 1;
document.write(numberofways(n, m));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3