用大于或等于m的数求和n的不同方法

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定两个自然数n和m。任务是找出大于或等于m的数相加得到n的几种方法。

例子：

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

输出如下：

3