# 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}.

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}.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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:

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 ` `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

 ` ``\$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
```