Tile Stacking Problem
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:
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 = 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 )] # 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> |
Output
7
Time Complexity: O(m*n)
Auxiliary Space: O(n*n)