本文概述
- C/C++
- Java
- python
- C#
- 的PHP
例子：
Input : n = 5
Output : 6
Explanation : All possible six ways are :
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1Input : 4
Output : 4
Explanation : All possible four ways are :
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1这个问题可以通过与硬币找零问题, 不同之处仅在于, 在这种情况下, 我们应该迭代1到n-1, 而不是像硬币找零问题那样重复特定的硬币值。
C/C++
// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
#include <
bits/stdc++.h>
using namespace std;
// Returns number of ways to write n as sum of
// two or more positive integers
int countWays( int n)
{
// table[i] will be storing the number of
// solutions for value i. We need n+1 rows
// as the table is consturcted in bottom up
// manner using the base case (n = 0)
int table[n+1];
// Initialize all table values as 0
memset (table, 0, sizeof (table));
// Base case (If given value is 0)
table[0] = 1;
// Pick all integer one by one and update the
// table[] values after the index greater
// than or equal to n
for ( int i=1;
i<
n;
i++)
for ( int j=i;
j<
=n;
j++)
table[j] += table[j-i];
return table[n];
}// Driver program
int main()
{
int n = 7;
cout <
<
countWays(n);
return 0;
}Java
// Program to find the number of ways, // n can be written as sum of two or
// more positive integers.
import java.util.Arrays;
class GFG {// Returns number of ways to write
// n as sum of two or more positive
// integers
static int countWays( int n)
{// table[i] will be storing the
// number of solutions for value
// i. We need n+1 rows as the
// table is consturcted in bottom
// up manner using the base case
// (n = 0)
int table[] = new int [n + 1 ];
// Initialize all table values as 0
Arrays.fill(table, 0 );
// Base case (If given value is 0)
table[ 0 ] = 1 ;
// Pick all integer one by one and
// update the table[] values after
// the index greater than or equal
// to n
for ( int i = 1 ;
i <
n;
i++)
for ( int j = i;
j <
= n;
j++)
table[j] += table[j - i];
return table[n];
}//driver code
public static void main (String[] args)
{
int n = 7 ;
System.out.print(countWays(n));
}
}// This code is contributed by Anant Agarwal.python
# Program to find the number of ways, n can be
# written as sum of two or more positive integers.# Returns number of ways to write n as sum of
# two or more positive integers
def CountWays(n):# table[i] will be storing the number of
# solutions for value i. We need n+1 rows
# as the table is consturcted in bottom up
# manner using the base case (n = 0)
# Initialize all table values as 0
table = [ 0 ] * (n + 1 )# Base case (If given value is 0)
# Only 1 way to get 0 (select no integer)
table[ 0 ] = 1# Pick all integer one by one and update the
# table[] values after the index greater
# than or equal to n
for i in range ( 1 , n ):for j in range (i , n + 1 ):table[j] + =table[j - i]return table[n]# driver program
def main():n = 7print CountWays(n)if __name__ = = '__main__' :
main()#This code is contributed by Neelam YadavC#
// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
using System;
class GFG {// Returns number of ways to write n as sum of
// two or more positive integers
static int countWays( int n)
{// table[i] will be storing the number of
// solutions for value i. We need n+1 rows
// as the table is consturcted in bottom up
// manner using the base case (n = 0)
int []table = new int [n+1];
// Initialize all table values as 0
for ( int i = 0;
i <
table.Length;
i++)
table[i] = 0;
// Base case (If given value is 0)
table[0] = 1;
// Pick all integer one by one and update the
// table[] values after the index greater
// than or equal to n
for ( int i = 1;
i <
n;
i++)
for ( int j = i;
j <
= n;
j++)
table[j] += table[j-i];
return table[n];
}//driver code
public static void Main()
{
int n = 7;
Console.Write(countWays(n));
}
}// This code is contributed by Anant Agarwal.的PHP
<
?php
// Program to find the number of ways, n can be
// written as sum of two or more positive integers.// Returns number of ways to write n as sum
// of two or more positive integers
function countWays( $n )
{
// table[i] will be storing the number of
// solutions for value i. We need n+1 rows
// as the table is consturcted in bottom up
// manner using the base case (n = 0)
$table = array_fill (0, $n + 1, NULL);
// Base case (If given value is 0)
$table [0] = 1;
// Pick all integer one by one and update
// the table[] values after the index
// greater than or equal to n
for ( $i = 1;
$i <
$n ;
$i ++)
for ( $j = $i ;
$j <
= $n ;
$j ++)
$table [ $j ] += $table [ $j - $i ];
return $table [ $n ];
}// Driver Code
$n = 7;
echo countWays( $n );
// This code is contributed by ita_c
?>
输出如下：
14时间复杂度O(n2)
【将n写为两个或多个正整数之和的方法】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 通过删除0个或多个字符将一个字符串转换为其他字符串的方法
- Java使用3种方法从控制台读取输入
- 为偏斜树着色的方法，以使父级和子级具有不同的颜色
- 排列球以使相邻球为不同类型的方式
- 使用允许重复的数组元素求和到N的方法
- 分割字符串的方法，以便每个分区以不同的字符开头
- C++标准模板库(STL)中的列表用法详细介绍
- 从二进制字符串中删除一个元素，使XOR变为0的方法
- 萝卜家园系统win732位介绍