本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
例子：
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这个想法是通过定义2D矩阵(例如dp [] [])来使用动态规划。dp [i] [j]使用大于或等于j的数字定义获取和i的方式的数量。因此dp [i] [j]可定义为：
如果i < j, 则dp [i] [j] = 0, 因为我们无法使用大于或等于j的数字来实现i的较小和。以下是此方法的实现：
如果i = j, 则dp [i] [j] = 1, 因为只有一种方法可以使用等于j的数字i来显示和i。
否则dp [i] [j] = dp [i] [j + 1] + dp [ij] [j], 因为使用大于或等于j的数字
获得和i等于获得… 的和。 i使用大于或等于j + 1的数字, 并使用大于或等于j的数字获得ij的总和。
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 RyugaC#
//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
?>
输出如下：
3推荐阅读
- 用Java读取文本文件的不同方法有哪些（）
- Java中方法重载的不同方法有哪些（）
- Java中整数到字符串转换的不同方法有哪些（）
- 在C和C++中将变量声明为常量的不同方法
- 用Java创建对象的不同方法有哪些（）
- 不同类型的RAM（随机存取存储器）
- 不同类型的聚类算法详细介绍
- 矩阵的不同运算快速介绍
- 用C++ STL复制的不同方法std::copy()、copy_n()、copy_if()、copy_backward()