动态规划解法讲解

Question

这就是问题所在：给定块数 n（3 到 200 之间），返回可以建造的不同楼梯的数量。每种类型的楼梯应包含 2 个或更多台阶。不允许有两个台阶处于相同高度 - 每个台阶必须低于前一个台阶。所有台阶必须至少包含一块砖块。台阶的高度被分类为组成该台阶的砖块的总数。

例如，当N = 3时，您只有1种选择如何建造楼梯，第一步的高度为2，第二步的高度为1：（#表示一块砖）

#
## 
21

当 N = 4 时，你仍然只有 1 个楼梯选择：

#
#
##
31

但是当 N = 5 时，有两种方法可以用给定的砖块建造楼梯。两个楼梯的高度可以为 (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;

    }

}

特别是，如何得出数组中每个连续条目之间的关系？

Answer 1

这是一个非常有趣的问题。首先，让我们尝试理解递归关系：

如果我们当前建造了一个高度的台阶h，并且还有b剩余的砖块可以使用，那么从这里开始完成楼梯的方法数等于我们可以用下一步的高度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));
  }
}

从您提供的代码来看，作者似乎更进一步，用纯迭代版本替换了递归解决方案。这意味着作者提出了自下而上的解决方案，而不是自上而下的解决方案。

我们还可以用更数学的方式来解决这个问题：

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

因此对于n = 6，我们有：5 + 1, 4 + 2, 3 + 2 + 1。所以answer(6) = 3。有趣的是，欧拉证明给定的不同整数分区的数量n始终与不一定不同的奇数整数分区的数量相同。

（顺便说一句，我知道这个问题从何而来。祝你好运！）