稳定的高塔 N 是一座由n块单位高度的瓷砖垂直堆叠而成的塔，这样一来，较小的瓷砖上就不会有较大的瓷砖。下面是一个例子：
null
![图片[1]-瓷砖堆放问题-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_9-6-1.png)
我们有无限多个大小为1、2、…、m的瓷砖。我们的任务是计算可以用这些瓷砖建造的高度为n的不同稳定塔楼的数量，限制条件是最多可以使用 K 塔中每种尺寸的瓷砖。 注： 当且仅当存在高度h（1<=h<=n）时，两个高度为n的塔是不同的，因此两个塔在高度h处具有不同尺寸的瓷砖。 例如：
Input : n = 3, m = 3, k = 1.Output : 1Possible sequences: { 1, 2, 3}. Hence answer is 1.Input : n = 3, m = 3, k = 2.Output : 7{1, 1, 2}, {1, 1, 3}, {1, 2, 2},{1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2, 3, 3}.
我们基本上需要使用从1到m的数字来计算长度n的递减序列，其中每个数字最多可以使用k次。我们可以使用n-1的计数递归地计算n的计数。 其思想是使用动态规划。声明一个2D数组dp[]]，其中每个状态dp[i][j]表示长度i的递减序列的数量，使用从j到m的数字。我们需要注意一个事实，即一个数字可以在k个时间的大部分时间内使用。这可以通过考虑数字的1到k次出现来实现。因此，我们的递归关系变成： ![{huge DP[i][j] = sum_{x=0}^{k}[i-x][j-1]}](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-00d6d7ad528021712d0d938a3ccac9fc_l3.png "Rendered by QuickLaTeX.com")
此外，我们可以利用一个事实，即对于一个固定的j，我们使用i的前k个值的连续值。因此，我们可以为每个状态维护一个前缀和数组。现在我们已经去掉了每个状态的k因子。 以下是该方法的实施情况：
C++
// CPP program to find number of ways to make stable // tower of given height. #include <bits/stdc++.h> using namespace std; #define N 100 int possibleWays( int n, int m, int k) { int dp[N][N]; int presum[N][N]; memset (dp, 0, sizeof dp); memset (presum, 0, sizeof presum); // Initialing 0th row to 0. for ( int i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initialing 0th column to 0. for ( int i = 0; i < m + 1; i++) presum[i][0] = dp[i][0] = 1; // For each row from 1 to m for ( int i = 1; i < m + 1; i++) { // For each column from 1 to n. for ( int j = 1; j < n + 1; j++) { // Initialing dp[i][j] to presum of (i - 1, j). dp[i][j] = presum[i - 1][j]; if (j > k) { dp[i][j] -= presum[i - 1][j - k - 1]; } } // Calculating presum for each i, 1 <= i <= n. for ( int j = 1; j < n + 1; j++) presum[i][j] = dp[i][j] + presum[i][j - 1]; } return dp[m][n]; } // Driver Program int main() { int n = 3, m = 3, k = 2; cout << possibleWays(n, m, k) << endl; return 0; } |
JAVA
// Java program to find number of ways to make // stable tower of given height. class GFG { static int N = 100 ; static int possibleWays( int n, int m, int k) { int [][] dp = new int [N][N]; int [][] presum = new int [N][N]; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { dp[i][j] = 0 ; presum[i][j] = 0 ; } } // Initialing 0th row to 0. for ( int i = 1 ; i < n + 1 ; i++) { dp[ 0 ][i] = 0 ; presum[ 0 ][i] = 1 ; } // Initialing 0th column to 0. for ( int i = 0 ; i < m + 1 ; i++) { presum[i][ 0 ] = dp[i][ 0 ] = 1 ; } // For each row from 1 to m for ( int i = 1 ; i < m + 1 ; i++) { // For each column from 1 to n. for ( int j = 1 ; j < n + 1 ; j++) { // Initialing dp[i][j] to presum of (i - 1, j). dp[i][j] = presum[i - 1 ][j]; if (j > k) { dp[i][j] -= presum[i - 1 ][j - k - 1 ]; } } // Calculating presum for each i, 1 <= i <= n. for ( int j = 1 ; j < n + 1 ; j++) { presum[i][j] = dp[i][j] + presum[i][j - 1 ]; } } return dp[m][n]; } // Driver Program public static void main(String[] args) { int n = 3 , m = 3 , k = 2 ; System.out.println(possibleWays(n, m, k)); } } // This code has been contributed by 29AjayKumar |
Python 3
# Python3 code to find number of ways # to make stable tower of given height n = 100 def possibleWays(n, m, k): dp = [[ 0 for i in range ( 10 )] for j in range ( 10 )] presum = [[ 0 for i in range ( 10 )] for j in range ( 10 )] # initialing 0th row to 0 for i in range ( 1 , n + 1 ): dp[ 0 ][i] = 0 presum[ 0 ][i] = 1 # initialing 0th column to 0 for i in range ( 0 , m + 1 ): presum[i][ 0 ] = 1 dp[i][ 0 ] = 1 # for each from 1 to m for i in range ( 1 , m + 1 ): # for each column from 1 to n. for j in range ( 1 , n + 1 ): # for each column from 1 to n # Initialing dp[i][j] to presum # of (i-1,j). dp[i][j] = presum[i - 1 ][j] if j > k: dp[i][j] - = presum[i - 1 ][j - k - 1 ] for j in range ( 1 , n + 1 ): presum[i][j] = dp[i][j] + presum[i][j - 1 ] return dp[m][n] # Driver Code n, m, k = 3 , 3 , 2 print (possibleWays(n, m, k)) # This code is contributed # by Mohit kumar 29 |
C#
// C# program to find number of ways to make // stable tower of given height. using System; class GFG { static int N = 100 ; static int possibleWays( int n, int m, int k) { int [,] dp = new int [N, N]; int [,] presum = new int [N, N]; for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { dp[i, j] = 0; presum[i, j] = 0; } } // Initialing 0th row to 0. for ( int i = 1; i < n + 1; i++) { dp[0, i] = 0; presum[0, i] = 1; } // Initialing 0th column to 0. for ( int i = 0; i < m + 1; i++) presum[i, 0] = dp[i, 0] = 1; // For each row from 1 to m for ( int i = 1; i < m + 1; i++) { // For each column from 1 to n. for ( int j = 1; j < n + 1; j++) { // Initialing dp[i][j] to presum of (i - 1, j). dp[i, j] = presum[i - 1, j]; if (j > k) { dp[i, j] -= presum[i - 1, j - k - 1]; } } // Calculating presum for each i, 1 <= i <= n. for ( int j = 1; j < n + 1; j++) presum[i, j] = dp[i, j] + presum[i, j - 1]; } return dp[m, n]; } // Driver Program static void Main() { int n = 3, m = 3, k = 2; Console.Write(possibleWays(n, m, k)); } } // This code is contributed by DrRoot_ |
<?php// PHP program to find number of ways to make stable // tower of given height. function possibleWays($n, $m, $k) { $N = 100 ; $dp = array(array()); for ($i = 0; $i < $N; $i++) for($j = 0; $j < $N; $j++) $dp[$i][$j] = 0 ; $presum = array(array()) ; for ($i = 0; $i < $N; $i++) for($j = 0; $j < $N; $j++) $presum[$i][$j] = 0 ; // Initialing 0th row to 0. for ($i = 1; $i < $n + 1; $i++) { $dp[0][$i] = 0; $presum[0][$i] = 1; } // Initialing 0th column to 0. for ($i = 0; $i < $m + 1; $i++) $presum[$i][0] = $dp[$i][0] = 1; // For each row from 1 to m for ($i = 1; $i < $m + 1; $i++) { // For each column from 1 to n. for ($j = 1; $j < $n + 1; $j++) { // Initialing dp[i][j] to presum of (i - 1, j). $dp[$i][$j] = $presum[$i - 1][$j]; if ($j > $k) { $dp[$i][$j] -= $presum[$i - 1][$j - $k - 1]; } } // Calculating presum for each i, 1 <= i <= n. for ($j = 1; $j < $n + 1; $j++) $presum[$i][$j] = $dp[$i][$j] + $presum[$i][$j - 1]; } return $dp[$m][$n]; } // Driver Program $n = 3 ; $m = 3 ; $k = 2; echo possibleWays($n, $m, $k) ; # this code is contributed by Ryuga ?>
Javascript
<script> // Javascript program to find // number of ways to make // stable tower of given height let N = 100; function possibleWays(n, m, k) { let dp = new Array(N); // Loop to create 2D array // using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } let presum = new Array(N); // Loop to create 2D array using 1D array for ( var i = 0; i < presum.length; i++) { presum[i] = new Array(2); } for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { dp[i][j] = 0; presum[i][j] = 0; } } // Initialing 0th row to 0. for (let i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initialing 0th column to 0. for (let i = 0; i < m + 1; i++) { presum[i][0] = dp[i][0] = 1; } // For each row from 1 to m for (let i = 1; i < m + 1; i++) { // For each column from 1 to n. for (let j = 1; j < n + 1; j++) { // Initialing dp[i][j] to // presum of (i - 1, j). dp[i][j] = presum[i - 1][j]; if (j > k) { dp[i][j] -= presum[i - 1][j - k - 1]; } } // Calculating presum for each // i, 1 <= i <= n. for (let j = 1; j < n + 1; j++) { presum[i][j] = dp[i][j] + presum[i][j - 1]; } } return dp[m][n]; } // driver program let n = 3, m = 3, k = 2; document.write(possibleWays(n, m, k)); </script> |
输出：
7
本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
