给定一个数n（变量数）和val（变量之和），找出有多少这样的非负积分解是可能的。
null
例如：
Input : n = 5, val = 1Output : 5Explanation:x1 + x2 + x3 + x4 + x5 = 1Number of possible solution are : (0 0 0 0 1), (0 0 0 1 0), (0 0 1 0 0),(0 1 0 0 0), (1 0 0 0 0)Total number of possible solutions are 5Input : n = 5, val = 4Output : 70Explanation:x1 + x2 + x3 + x4 + x5 = 4Number of possible solution are: (1 1 1 1 0), (1 0 1 1 1), (0 1 1 1 1), (2 1 0 0 1), (2 2 0 0 0)........ so on......Total numbers of possible solutions are 70
问：微软采访
1.对countSolutions（int n，int val）进行递归函数调用 2.调用此解函数countSolutions（n-1，val-i），直到n=1且val>=0，然后返回1。
以下是上述方法的实施情况：
C++
// CPP program to find the numbers // of non negative integral solutions #include<iostream> using namespace std; // return number of non negative // integral solutions int countSolutions( int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) return 1; // iterate the loop till equal the val for ( int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // return the total no possible solution return total; } // driver code int main(){ int n = 5; int val = 20; cout<<countSolutions(n, val); } //This code is contributed by Smitha Dinesh Semwal |
JAVA
// Java program to find the numbers // of non negative integral solutions class GFG { // return number of non negative // integral solutions static int countSolutions( int n, int val) { // initialize total = 0 int total = 0 ; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0 ) return 1 ; // iterate the loop till equal the val for ( int i = 0 ; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1 , val - i); } // return the total no possible solution return total; } // Driver code public static void main(String[] args) { int n = 5 ; int val = 20 ; System.out.print(countSolutions(n, val)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find the numbers # of non negative integral solutions # return number of non negative # integral solutions def countSolutions(n, val): # initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n = = 1 and val > = 0 : return 1 # iterate the loop till equal the val for i in range (val + 1 ): # total solution of equations # and again call the recursive # function Solutions(variable,value) total + = countSolutions(n - 1 , val - i) # return the total no possible solution return total # driver code n = 5 val = 20 print (countSolutions(n, val)) |
C#
// C# program to find the numbers // of non negative integral solutions using System; class GFG { // return number of non negative // integral solutions static int countSolutions( int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // iterate the loop till equal the val for ( int i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return total; } // Driver code public static void Main() { int n = 5; int val = 20; Console.WriteLine(countSolutions(n, val)); } } // This code is contributed by Anant vt_m. |
PHP
<?php // PHP program to find the numbers // of non negative integral solutions // return number of non negative // integral solutions function countSolutions( $n , $val ) { // initialize total = 0 $total = 0; // Base Case if n = 1 and // val >= 0 then it should // return 1 if ( $n == 1 && $val >=0) return 1; // iterate the loop // till equal the val for ( $i = 0; $i <= $val ; $i ++) { // total solution of equations // and again call the recursive // function Solutions(variable,value) $total += countSolutions( $n - 1, $val - $i ); } // return the total // no possible solution return $total ; } // Driver Code $n = 5; $val = 20; echo countSolutions( $n , $val ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // JavaScript program to find the numbers // of non negative integral solutions // return number of non negative // integral solutions function countSolutions(n, val) { // initialize total = 0 let total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // iterate the loop till equal the val for (let i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return total; } // Driver code let n = 5; let val = 20; document.write(countSolutions(n, val)); </script> |
输出：
10626
动态规划方法：
（使用备忘录）
C++
// CPP program to find the numbers // of non negative integral solutions #include<bits/stdc++.h> using namespace std; int dp[1001][1001]; // return number of non negative // integral solutions int countSolutions( int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) { return 1; } // If a value already present in dp, // return it if (dp[n][val] != -1) { return dp[n][val]; } // iterate the loop till equal the val for ( int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // Store the value in dp dp[n][val] = total; // Return dp return dp[n][val]; } // driver code int main(){ int n = 5; int val = 20; memset (dp, -1, sizeof (dp)); cout << countSolutions(n, val); } |
JAVA
// Java program to find the numbers // of non negative integral solutions import java.util.*; public class GFG { static int dp[][] = new int [ 1001 ][ 1001 ]; // return number of non negative // integral solutions static int countSolutions( int n, int val) { // initialize total = 0 int total = 0 ; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0 ) { return 1 ; } // If a value already present in dp, // return it if (dp[n][val] != - 1 ) { return dp[n][val]; } // iterate the loop till equal the val for ( int i = 0 ; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n- 1 , val-i); } // Store the value in dp dp[n][val] = total; // Return dp return dp[n][val]; } // driver code public static void main(String args[]){ int n = 5 ; int val = 20 ; for ( int i = 0 ; i < 1001 ; i++) { for ( int j = 0 ; j < 1001 ; j++) { dp[i][j]=- 1 ; } } System.out.println(countSolutions(n, val)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 program to find the numbers # of non negative integral solutions # Taking the matrix as globally dp = [[ - 1 for i in range ( 1001 )] for j in range ( 1001 )] # Return number of non negative # integral solutions def countSolutions(n, val): # Initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n = = 1 and val > = 0 : return 1 # If a value is already present # in dp if (dp[n][val] ! = - 1 ): return dp[n][val] # Iterate the loop till equal the val for i in range (val + 1 ): # total solution of equations # and again call the recursive # function Solutions(variable,value) total + = countSolutions(n - 1 , val - i) # Return the total no possible solution dp[n][val] = total return dp[n][val] # Driver code n = 5 val = 20 print (countSolutions(n, val)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program to find the numbers // of non negative integral solutions using System; class GFG { static int [,]dp = new int [1001, 1001]; // return number of non negative // integral solutions static int countSolutions( int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) { return 1; } // If a value already present in dp, // return it if (dp[n, val] != -1) { return dp[n, val]; } // iterate the loop till equal the val for ( int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // Store the value in dp dp[n, val] = total; // Return dp return dp[n, val]; } // driver code public static void Main(){ int n = 5; int val = 20; for ( int i = 0; i < 1001; i++) { for ( int j = 0; j < 1001; j++) { dp[i, j] = -1; } } Console.Write(countSolutions(n, val)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to find the numbers // of non negative integral solutions var dp = new Array(1001); // Loop to create 2D array using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(1001); } // return number of non negative // integral solutions function countSolutions(n, val) { // initialize total = 0 let total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // if a value is already // present in dp if (dp[n][val] != -1) return dp[n][val]; // iterate the loop till equal the val for (let i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return dp[n][val] = total; } // Driver code let n = 5; let val = 20; for (let i = 0; i < 1001; i++) { for (let j = 0; j < 1001; j++) { dp[i][j] = -1; } } document.write(countSolutions(n, val)); // This code is contributed by Samim Hossain Mondal. </script> |
输出
10626
时间复杂性： O（n*val）
辅助空间： O（n*val）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
