这就是问题所在:给定 3 到 200 之间的砖 block 数量 n，返回可以 build 的不同楼梯的数量。每种类型的楼梯应由 2 个或更多台阶组成。不允许两级台阶高度相同——每级台阶都必须低于前一级。所有步骤必须至少包含一 block 砖。台阶的高度被归类为构成该台阶的砖 block 总数。
例如，当N=3时，楼梯的搭建方式只有一种选择，第一步高度为2，第二步高度为1:(#表示砖)
#
##
21
当 N = 4 时，您仍然只有 1 个楼梯选择:
#
#
##
31
但是当 N = 5 时，有两种方法可以用给定的砖 block build 楼梯。两个楼梯的高度可以是(4, 1) 或(3, 2)，如下图:
#
#
#
##
41
#
##
##
32
网上找了个解法，但是对动态规划的解法不是很直观。
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;
}
}
特别是，如何得出数组中每个连续条目之间的关系？
最佳答案
这是一个非常有趣的问题。首先，让我们尝试了解 recurrence relation :
如果我们目前构建了一个高度为h的台阶我们有b剩下的砖 block ，我们可以从这里完成楼梯的方式的数量等于我们可以完成下一步高度楼梯的所有方式的总和h'和 b - h'砖，用于 0 < h' < h .
一旦我们有了这个递推关系，我们就可以设计一个递归解决方案；但是，在当前状态下，解决方案以指数时间运行。所以，我们只需要“缓存”我们的结果:
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));
}
}
从你提供的代码来看，作者似乎更进了一步，用纯迭代的版本代替了递归的解决方案。这意味着作者做了一个bottom-up solution rather than a top-down solution .
我们还可以更数学地处理这个问题:
How many distinct non-trivial integer partitions does n have?
所以对于 n = 6 ，我们有:5 + 1 , 4 + 2 , 3 + 2 + 1 .所以answer(6) = 3 .有趣的是，Euler proved给定 n 的不同整数分区的数量总是与不一定不同的奇整数分区的数量相同。
(作为旁注，我知道这个问题来自哪里。祝你好运!)
关于java - 动态规划解法讲解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44508211/