使用允许重复的数组元素求和到N的方法

2021年4月4日18:58:55 发表评论 755 次浏览

本文概述

C ++
Java
Python3
C#
的PHP

给定一组m个不同的正整数和值"N"。问题在于计算通过对数组元素求和形成"N"的总数。允许重复和不同的安排。

例子：

Input : arr = {1, 5, 6}, N = 7
Output : 6

Explanation:- The different ways are:
1+1+1+1+1+1+1
1+1+5
1+5+1
5+1+1
1+6
6+1

Input : arr = {12, 3, 1, 9}, N = 14
Output : 150

方法：该方法基于动态编程的概念。

countWays(arr, m, N)
        Declare and initialize count[N + 1] = {0}
        count[0] = 1
        for i = 1 to N
            for j = 0 to m - 1
                if i >= arr[j]
                   count[i] += count[i - arr[j]]
        return count[N]

下面是上述方法的实现。

C ++

// C++ implementation to count ways 
// to sum up to a given value N
#include <bits/stdc++.h>
  
using namespace std;
  
// function to count the total 
// number of ways to sum up to 'N'
int countWays( int arr[], int m, int N)
{
     int count[N + 1];
     memset (count, 0, sizeof (count));
      
     // base case
     count[0] = 1;
      
     // count ways for all values up 
     // to 'N' and store the result
     for ( int i = 1; i <= N; i++)
         for ( int j = 0; j < m; j++)
  
             // if i >= arr[j] then
             // accumulate count for value 'i' as
             // ways to form value 'i-arr[j]'
             if (i >= arr[j])
                 count[i] += count[i - arr[j]];
      
     // required number of ways 
     return count[N]; 
      
}
  
// Driver code
int main()
{
     int arr[] = {1, 5, 6};
     int m = sizeof (arr) / sizeof (arr[0]);
     int N = 7;
     cout << "Total number of ways = "
         << countWays(arr, m, N);
     return 0;
}

Java

// Java implementation to count ways  
// to sum up to a given value N
  
class Gfg
{
     static int arr[] = { 1 , 5 , 6 };
      
     // method to count the total number
     // of ways to sum up to 'N'
     static int countWays( int N)
     {
         int count[] = new int [N + 1 ];
          
         // base case
         count[ 0 ] = 1 ;
          
         // count ways for all values up 
         // to 'N' and store the result
         for ( int i = 1 ; i <= N; i++)
             for ( int j = 0 ; j < arr.length; j++)
      
                 // if i >= arr[j] then
                 // accumulate count for value 'i' as
                 // ways to form value 'i-arr[j]'
                 if (i >= arr[j])
                     count[i] += count[i - arr[j]];
          
         // required number of ways 
         return count[N]; 
          
     }
      
     // Driver code
     public static void main(String[] args) 
     {
         int N = 7 ;
         System.out.println( "Total number of ways = "
                                     + countWays(N));
     }
}

Python3

# Python3 implementation to count 
# ways to sum up to a given value N
  
# Function to count the total 
# number of ways to sum up to 'N'
def countWays(arr, m, N):
  
     count = [ 0 for i in range (N + 1 )]
      
     # base case
     count[ 0 ] = 1
      
     # Count ways for all values up 
     # to 'N' and store the result
     for i in range ( 1 , N + 1 ):
         for j in range (m):
  
             # if i >= arr[j] then
             # accumulate count for value 'i' as
             # ways to form value 'i-arr[j]'
             if (i > = arr[j]):
                 count[i] + = count[i - arr[j]]
      
     # required number of ways 
     return count[N]
      
# Driver Code
arr = [ 1 , 5 , 6 ]
m = len (arr)
N = 7
print ( "Total number of ways = " , countWays(arr, m, N))
             
# This code is contributed by Anant Agarwal.

C#

// C# implementation to count ways  
// to sum up to a given value N
using System;
  
class Gfg
{
     static int []arr = {1, 5, 6};
      
     // method to count the total number
     // of ways to sum up to 'N'
     static int countWays( int N)
     {
         int []count = new int [N+1];
          
         // base case
         count[0] = 1;
          
         // count ways for all values up 
         // to 'N' and store the result
         for ( int i = 1; i <= N; i++)
             for ( int j = 0; j < arr.Length; j++)
      
                 // if i >= arr[j] then
                 // accumulate count for value 'i' as
                 // ways to form value 'i-arr[j]'
                 if (i >= arr[j])
                     count[i] += count[i - arr[j]];
          
         // required number of ways 
         return count[N]; 
          
     }
      
     // Driver code
     public static void Main() 
     {
         int N = 7;
         Console.Write( "Total number of ways = "
                                     + countWays(N));
     }
}
  
//This code is contributed by nitin mittal.

的PHP

<?php
// PHP implementation to count ways 
// to sum up to a given value N 
  
// function to count the total 
// number of ways to sum up to 'N' 
function countWays( $arr , $m , $N ) 
{ 
     $count = array_fill (0, $N + 1, 0); 
      
     // base case 
     $count [0] = 1; 
      
     // count ways for all values up 
     // to 'N' and store the result 
     for ( $i = 1; $i <= $N ; $i ++) 
         for ( $j = 0; $j < $m ; $j ++) 
  
             // if i >= arr[j] then 
             // accumulate count for value 'i' as 
             // ways to form value 'i-arr[j]' 
             if ( $i >= $arr [ $j ]) 
                 $count [ $i ] += $count [ $i - $arr [ $j ]]; 
      
     // required number of ways 
     return $count [ $N ]; 
      
} 
  
// Driver code 
$arr = array (1, 5, 6); 
$m =  count ( $arr );
$N = 7;
echo "Total number of ways = " , countWays( $arr , $m , $N ); 
  
// This code is contributed by Ryuga
?>

输出如下：