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?
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!)