A stable tower of height n is a tower consisting of exactly n tiles of unit height stacked vertically in such a way, that no bigger tile is placed on a smaller tile.
An example is shown below :
We have an infinite number of tiles of sizes 1, 2, …, m. The task is to calculate the number of the different stable towers of height n that can be built from these tiles, with a restriction that you can use at most k tiles of each size in the tower.
Note: Two towers of height n are different if and only if there exists a height h (1 <= h <= n), such that the towers have tiles of different sizes at height h.
Examples:
Input : n = 3, m = 3, k = 1.
Output : 1
Possible 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}.
We basically need to count a number of decreasing sequences of length n using numbers from 1 to m where every number can be used at most k times. We can recursively compute count for n using count for n-1.
The idea is to use Dynamic Programming. Declare a 2D array dp[][], where each state dp[i][j] denotes the number of decreasing sequences of length i using numbers from j to m. We need to take care of the fact that a number can be used most of k time. This can be done by considering 1 to k occurrences of a number. Hence, our recurrence relation becomes: ![{\huge DP[i][j] = \sum_{x=0}^{k}[i-x][j-1]}](https://neveropen.co.za/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-d20f4c640756ca0d20ca77c32d2b1f5a_l3.png "Rendered by QuickLaTeX.com")
Also, we can use the fact that for a fixed j we are using the consecutive values of previous k values of i. Hence, we can maintain a prefix sum array for each state. Now we have gotten rid of the k factor for each state.
Below is the implementation of this approach:
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); // Initializing 0th row to 0. for (int i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initializing 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++) { // Initializing 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. import java.io.*; 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; } } // Initializing 0th row to 0. for (int i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initializing 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++) { // Initializing 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 = 100def 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)] # Initializing 0th row to 0 for i in range(1, n + 1): dp[0][i] = 0 presum[0][i] = 1 # Initializing 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 # Initializing 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; } } // Initializing 0th row to 0. for (int i = 1; i < n + 1; i++) { dp[0, i] = 0; presum[0, i] = 1; } // Initializing 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++) { // Initializing 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 // 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 ; // Initializing 0th row to 0. for ($i = 1; $i < $n + 1; $i++) { $dp[0][$i] = 0; $presum[0][$i] = 1; } // Initializing 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++) { // Initializing 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; } } // Initializing 0th row to 0. for (let i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initializing 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++) { // Initializing 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
Time Complexity: O(m*n)
Auxiliary Space: O(n*n)
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using contribute.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
