Explanation of Dynamic Programming solution

Question

This is the problem: given a number of bricks n, between 3 and 200, return the number of different staircases that can be built. Each type of staircase should consist of 2 or more steps. No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step's height is classified as the total amount of bricks that make up that step.

For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

#
## 
21

When N = 4, you still only have 1 staircase choice:

#
#
##
31

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

#
#
#
##
41

#
##
##
32

I found a solution online, but I don't quite intuitively understand the dynamic programming solution.

public class Answer {

    static int[][] p = new int[201][201];

    public static void fillP() {
        p[1][1] = 1;
        p[2][2] = 1;

        for (int w = 3; w < 201 ; w++) {
            for (int m = 1; m <= w; m++) {
                if (w-m == 0) {

                    p[w][m] = 1 + p[w][m-1];

                } else if (w-m < m) {   

                    p[w][m] =  p[w-m][w-m] + p[w][m-1];

                } else if (w-m == m) {  
                    p[w][m] = p[m][m-1] + p[w][m-1];

                } else if (w-m >m) { 

                    p[w][m] = p[w-m][m-1] + p[w][m-1];
                }

            }
        }
    }

    public static int answer(int n) {

        fillP();
        return p[n][n] - 1;

    }

}

In particular, how would one come up with the relationships between each successive entry in the array?

Answer 1

This is a very interesting question. First, let's try to understand the recurrence relation:

If we currently built a step of height h and we have b bricks left to use, the number of ways we could complete the staircase from here is equal to the sum of all the ways we can complete the staircase with the next step of height h' and b - h' bricks, for 0 < h' < h.

Once we have that recurrence relation, we can devise a recursive solution; however, at it's current state, the solution runs in exponential time. So, we just need to "cache" our results:

import java.util.Scanner;

public class Stairs {
  static int LIMIT = 200;
  static int DIRTY = -1;
  static int[][] cache = new int[LIMIT + 2][LIMIT + 2];

  public static void clearCache() {
    for (int i = 0; i <= LIMIT + 1; i++) {
      for (int j = 0; j <= LIMIT + 1; j++) {
        // mark cache as dirty/garbage values
        cache[i][j] = DIRTY;
      }
    }
  }

  public static int numberOfStaircases(int level, int bricks, int steps) {
    // base cases
    if (bricks < 0) return 0;
    if (bricks == 0 && steps >= 2) return 1;

    // only compute answer if we haven't already
    if (cache[level][bricks] == DIRTY) {
      int ways = 0;
      for (int nextLevel = level - 1; nextLevel > 0; nextLevel--) {
        ways += numberOfStaircases(nextLevel, bricks - nextLevel, steps + 1);
      }
      cache[level][bricks] = ways;
    }

    return cache[level][bricks];
  }

  public static int answer(int n) {
    clearCache();
    return numberOfStaircases(n + 1, n, 0);
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println(answer(n));
  }
}

From the code you provided, it seems as if the author went one more step further and replaced the recursive solution with a purely iterative version. This means that the author made a bottom-up solution rather than a top-down solution.

We could also approach the problem more mathematically:

How many distinct non-trivial integer partitions does n have?

So for n = 6, we have: 5 + 1, 4 + 2, 3 + 2 + 1. So answer(6) = 3. Interestingly enough, Euler proved that the number of distinct integer partitions for a given n is always the same as the number of not necessarily distinct odd integer partitions.

(As a side note, I know where this question comes from. Good luck!)

Answer 2

Good explanation of this problem (The Grandest Staircase Of Them All) is on the page with several different solutions.

https://jtp.io/2016/07/26/dynamic-programming-python.html

Answer 3

For building a staircase, we can consider it as a pyramid to build on top of each step with the amount of bricks that remain with us as we ascend and complete our staircase.

For n bricks we have, we can start with i bricks on top of the first step, which means we have n-i bricks remaining with us for the current step. As we calculate the number of ways for building a multilevel staircase of n bricks, for first step n-i, the number of ways are - to build the staircase with i bricks which can either be multilevel or a single step. We can follow this relative mechanism to get the total number of staircases that are possible from the zeroth step with n bricks.

To avoid calculating the same results for a pyramid of bricks i, we can use an in memory cache which stores results of the possible staircases for n bricks with k as its last step (since the possible staircases will depend on the previous step over which the pyramid will be placed just to avoid double steps or last step becoming smaller than the next one).

package com.dp;

import java.util.HashMap;
import java.util.Map;

public class Staircases {

private static Map<String, Long> cacheNumberStaircasesForNBricks = new HashMap<String, Long>();

public static void main(String[] args) {

    int bricks = 1000;
    Long start = System.currentTimeMillis();
    long numberOfStaircases = getStaircases(bricks, Integer.MAX_VALUE, true);
    Long end = System.currentTimeMillis();
    System.out.println(numberOfStaircases);
    System.out.println("Time taken " + (end - start) + " ms");

}

/*
 * For n bricks returns number of staircases can be formed with minimum 2
 * stairs and no double steps, with k as the number of bricks in last step
 */
private static long getStaircases(int n, int k, boolean multilevelOnly) {

    /*
     * if the last step was same as n, you can't get a single step of n bricks as the next step, 
     * hence the staircase needs to be multilevel
     */
    if (n == k) {

        multilevelOnly = true;
    }
    /*
     * for n less than 3 ie 1 or 2 there is only one stair case possible if the last step is of greater number of bricks
     */
    if (n < 3) {
        if (k <= n) {
            return 0;
        }
        return 1;
    }

    /*
     * for n =3, if multilevel is allowed only, then only one combination is
     * there ie 2,1.
     */
    if (n == 3) {
        if (k < n) {
            return 0;
        }
        if (multilevelOnly) {
            return 1;
        }
    }

    /*
     * refer from the in-memory cache. Don't compute if we have computed for last step (k) and current bricks left (n) to build the rest of the staircase
     */
    String cacheKey = n + "-" + k;
    if (cacheNumberStaircasesForNBricks.get(cacheKey) != null) {

        return cacheNumberStaircasesForNBricks.get(cacheKey);
    }

    /* 
     * start with one case which involves a single step of n bricks.
     * for multilevel only or last step being smaller(invalid scenario) staircases, put the initial count as zero 
     */
    long numberOfStaircases = multilevelOnly || k < n ? 0 : 1;

    for (int i = 1; n - i > 0; i++) {
         
        // current step must be smaller than the last step 
        if (n - i < k) {

            numberOfStaircases += getStaircases(i, n - i, false);
        }
    }

    cacheNumberStaircasesForNBricks.put(cacheKey, numberOfStaircases);
    return numberOfStaircases;
  }
}