考虑一个玩家可以在一个动作中得分3或5或10分的游戏。给定总分n，找出达到给定分数的方法。 例如：
null
Input: n = 20Output: 4There are following 4 ways to reach 20(10, 10)(5, 5, 10)(5, 5, 5, 5)(3, 3, 3, 3, 3, 5)Input: n = 13Output: 2There are following 2 ways to reach 13(3, 5, 5)(3, 10)
这个问题是 硬币兑换问题 可以在O（n）时间和O（n）辅助空间中求解。 其想法是创建一个大小为n+1的表，以存储从0到n的所有分数的计数。对于每个可能的移动（3、5和10），表中的增量值。
C++
// A C++ program to count number of // possible ways to a given score // can be reached in a game where a // move can earn 3 or 5 or 10 #include <iostream> using namespace std; // Returns number of ways // to reach score n int count( int n) { // table[i] will store count // of solutions for value i. int table[n + 1], i; // Initialize all table // values as 0 for ( int j = 0; j < n + 1; j++) table[j] = 0; // Base case (If given value is 0) table[0] = 1; // One by one consider given 3 moves // and update the table[] values after // the index greater than or equal to // the value of the picked move for (i = 3; i <= n; i++) table[i] += table[i - 3]; for (i = 5; i <= n; i++) table[i] += table[i - 5]; for (i = 10; i <= n; i++) table[i] += table[i - 10]; return table[n]; } // Driver Code int main( void ) { int n = 20; cout << "Count for " << n << " is " << count(n) << endl; n = 13; cout << "Count for " << n<< " is " << count(n) << endl; return 0; } // This code is contributed // by Shivi_Aggarwal |
C
// A C program to count number of possible ways to a given score // can be reached in a game where a move can earn 3 or 5 or 10 #include <stdio.h> // Returns number of ways to reach score n int count( int n) { // table[i] will store count of solutions for // value i. int table[n+1], i; // Initialize all table values as 0 memset (table, 0, sizeof (table)); // Base case (If given value is 0) table[0] = 1; // One by one consider given 3 moves and update the table[] // values after the index greater than or equal to the // value of the picked move for (i=3; i<=n; i++) table[i] += table[i-3]; for (i=5; i<=n; i++) table[i] += table[i-5]; for (i=10; i<=n; i++) table[i] += table[i-10]; return table[n]; } // Driver program int main( void ) { int n = 20; printf ( "Count for %d is %d" , n, count(n)); n = 13; printf ( "Count for %d is %d" , n, count(n)); return 0; } |
JAVA
// Java program to count number of // possible ways to a given score // can be reached in a game where // a move can earn 3 or 5 or 10 import java.util.Arrays; class GFG { // Returns number of ways to reach score n static int count( int n) { // table[i] will store count of solutions for // value i. int table[] = new int [n + 1 ], i; // Initialize all table values as 0 Arrays.fill(table, 0 ); // Base case (If given value is 0) table[ 0 ] = 1 ; // One by one consider given 3 // moves and update the table[] // values after the index greater // than or equal to the value of // the picked move for (i = 3 ; i <= n; i++) table[i] += table[i - 3 ]; for (i = 5 ; i <= n; i++) table[i] += table[i - 5 ]; for (i = 10 ; i <= n; i++) table[i] += table[i - 10 ]; return table[n]; } // Driver code public static void main (String[] args) { int n = 20 ; System.out.println( "Count for " +n+ " is " +count(n)); n = 13 ; System.out.println( "Count for " +n+ " is " +count(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to count number of possible ways to a given # score can be reached in a game where a move can earn 3 or # 5 or 10. # Returns number of ways to reach score n. def count(n): # table[i] will store count of solutions for value i. # Initialize all table values as 0. table = [ 0 for i in range (n + 1 )] # Base case (If given value is 0) table[ 0 ] = 1 # One by one consider given 3 moves and update the # table[] values after the index greater than or equal # to the value of the picked move. for i in range ( 3 , n + 1 ): table[i] + = table[i - 3 ] for i in range ( 5 , n + 1 ): table[i] + = table[i - 5 ] for i in range ( 10 , n + 1 ): table[i] + = table[i - 10 ] return table[n] # Driver Program n = 20 print ( 'Count for' , n, 'is' , count(n)) n = 13 print ( 'Count for' , n, 'is' , count(n)) # This code is contributed by Soumen Ghosh |
C#
// C# program to count number of // possible ways to a given score // can be reached in a game where // a move can earn 3 or 5 or 10 using System; class GFG { // Returns number of ways to reach // score n static int count( int n) { // table[i] will store count // of solutions for value i. int []table = new int [n + 1]; // Initialize all table values // as 0 for ( int j = 0; j < n+1; j++) table[j] = 0; // Base case (If given value is 0) table[0] = 1; // One by one consider given 3 // moves and update the table[] // values after the index greater // than or equal to the value of // the picked move for ( int i = 3; i <= n; i++) table[i] += table[i - 3]; for ( int i = 5; i <= n; i++) table[i] += table[i - 5]; for ( int i = 10; i <= n; i++) table[i] += table[i - 10]; return table[n]; } // Driver code public static void Main () { int n = 20; Console.WriteLine( "Count for " + n + " is " + count(n)); n = 13; Console.Write( "Count for " + n + " is " + count(n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to count number of // possible ways to a given score // can be reached in a game where // a move can earn 3 or 5 or 10 // Returns number of ways to reach // score n function counts( $n ) { // table[i] will store count // of solutions for value i. // Initialize all table // values as 0 for ( $j = 0; $j < $n + 1; $j ++) $table [ $j ] = 0; // Base case (If given value is 0) $table [0] = 1; // One by one consider given 3 moves // and update the table[] values after // the index greater than or equal to // the value of the picked move for ( $i = 3; $i <= $n ; $i ++) $table [ $i ] += $table [ $i - 3]; for ( $i = 5; $i <= $n ; $i ++) $table [ $i ] += $table [ $i - 5]; for ( $i = 10; $i <= $n ; $i ++) $table [ $i ] += $table [ $i - 10]; return $table [ $n ]; } // Driver Code $n = 20; echo "Count for " ; echo ( $n ); echo ( " is " ); echo counts( $n ); $n = 13; echo ( "" ) ; echo "Count for " ; echo ( $n ); echo ( " is " ); echo counts( $n ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // A JavaScript program to count number of // possible ways to a given score // can be reached in a game where a // move can earn 3 or 5 or 10 // Returns number of ways // to reach score n function count(n) { // table[i] will store count // of solutions for value i. let table = new Array(n + 1), i; // Initialize all table // values as 0 for (let j = 0; j < n + 1; j++) table[j] = 0; // Base case (If given value is 0) table[0] = 1; // One by one consider given 3 moves // and update the table[] values after // the index greater than or equal to // the value of the picked move for (i = 3; i <= n; i++) table[i] += table[i - 3]; for (i = 5; i <= n; i++) table[i] += table[i - 5]; for (i = 10; i <= n; i++) table[i] += table[i - 10]; return table[n]; } // Driver Code let n = 20; document.write( "Count for " + n + " is " + count(n) + "<br>" ); n = 13; document.write( "Count for " + n + " is " + count(n) + "<br>" ); // This code is contributed by Surbhi Tyagi. </script> |
输出：
Count for 20 is 4Count for 13 is 2
练习： 当（10,5,5）、（5,5,10）和（5,10,5）被视为不同的动作序列时，如何计算分数。同样，（5,3,3）、（3,5,3）和（3,3,5）被认为是不同的。 本文由 拉吉耶夫·阿罗拉 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
