Explanation of the dynamic programming solution
This is a problem: given the number of bricks n from 3 to 200, return the number of different stairs that can be built. Each type of ladder should have two or more steps. No two steps can be at the same height - each step must be lower than the previous one. All stages must contain at least one brick. The step height is classified as the total number of bricks that make up that step.
For example, when N = 3, you only have one choice of how to build the staircase, with the first step being 2 and the second step 1: (# stands for brick)
#
##
21
When N = 4, you only have 1 ladder choice left:
#
#
##
31
But when N = 5, you can build a staircase from these bricks in two ways. Two ladders can have heights (4, 1) or (3, 2), as shown below:
#
#
#
##
41
#
##
##
32
I found a solution on the internet, but I am not quite intuitive about a 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 the connections arise between each sequential record in the array?
source to share
This is a very interesting question. First, try to understand the repetition relationship :
If at the moment we have built a step in height h
, and we have bricks left b
, the number of ways that we could complete the stairs from here is equal to the sum of all the ways in which we can complete the stairs with the next step of heights h'
and b - h'
bricks, for 0 < h' < h
.
Once we have this recursive relationship, we can develop a recursive solution; however, in this 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 like the author went one step further and replaced the recursive solution with a purely iterative version. This means that the author has done from bottom to top, not top to bottom .
We could approach the problem mathematically:
How many distinct non-trivial integer partitions does n have?
So, n = 6
we have: 5 + 1
, 4 + 2
, 3 + 2 + 1
. So answer(6) = 3
. Interestingly, Euler proved that the number of distinct whole sections for a given is n
always the same as the number of not necessarily crisp odd whole sections.
(As a side note, I know where this question comes from. Good luck!)
source to share