动态规划解决方案的解释

Question

这是问题：给定一个介于3和200之间的砖块数n，返回可以构建的不同楼梯数量。每种类型的楼梯应包括2个或更多级别。不允许两级别处于相同高度-每一步必须比前一步低。所有步骤都必须至少包含一个砖块。一级别的高度被定义为组成该级别的所有砖块的总量。

例如，当N = 3时，您只有一种选择来构建楼梯，第一步高度为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;

    }

}

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

- Peter Wang

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));
  }
}

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

我们也可以更数学地解决问题：

n有多少个不同的非平凡整数划分？

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

（顺便说一句，我知道这个问题来自哪里。祝你好运！）

- ljeabmreosn

---

谢谢！ :) 这是一个有趣的挑战！ - Peter Wang

Answer 2

对于建造楼梯，我们可以将其视为一个金字塔，每一步都在上面堆砌剩余的砖块数量，直到完成整个楼梯。

对于我们拥有的n块砖，我们可以从第一步开始用i块砖，这意味着我们在当前步骤中还剩下n-i块砖。当我们计算n块砖的多层楼梯的建造方式时，对于第一步n-i，建造楼梯的方式有很多种，可以是多层或单层。我们可以按照这种相对机制来得到从零级台阶开始使用n块砖所能建造的所有楼梯的总数。

为了避免计算相同的金字塔砖块i的结果，我们可以使用内存缓存，存储n块砖的可能楼梯结果，其中k是最后一步（因为可能的楼梯将取决于之前的步骤，以避免重复步骤或最后一步变小于下一步）。

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;
  }
}

- Mukesh

---

最好将描述加入到你的代码中。 - ParisaN

Answer 3

这个问题（The Grandest Staircase Of Them All）的好解释在页面上有几种不同的解决方案。

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

- Jsowa