Tutorialspoint.dev

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 infinite number of tiles of sizes 1, 2, …, m. The task is calculate the number of different stable tower 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 tower 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 = 1.
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 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 a most k times. 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]}
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 got rid of the k factor for each state.

Below is the the implemantation 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);
  
    // 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;
}

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
// 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    
?>


Output:

7

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter