动态规划解法讲解

Question

这就是问题所在：给定砖块数量 n，在 3 到 200 之间，return 可以建造的不同楼梯的数量。每种类型的楼梯应由 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;

    }

}

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

Answer 1

这是一个非常有趣的问题。首先，让我们试着理解 recurrence relation:

如果我们目前建造了一个高度为 h 的台阶，并且我们还有 b 块积木可以使用，那么我们可以从这里完成楼梯的方法数等于所有方法的总和我们可以用下一步的高度 h' 和 b - h' 砖来完成楼梯的方法，用于 0 < h' < h.

一旦我们有了这个递推关系，我们就可以设计一个递归解决方案；但是，在当前状态下，解决方案以指数时间运行。所以，我们只需要 "cache" 我们的结果：

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 的不同整数分区的数量总是与不一定不同的奇整数分区的数量相同。

（作为旁注，我知道这个问题来自哪里。祝你好运！）

Answer 2

这个问题的很好的解释（最宏伟的楼梯）在页面上有几个不同的解决方案。

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

Answer 3

对于建造楼梯，我们可以将其视为金字塔，在每一步的顶部建造，并在我们上升并完成楼梯时留下大量的砖块。

对于我们有的 n 块砖，我们可以从第一步顶部的 i 块砖开始，这意味着我们在当前步骤中还剩下 n-i 块砖。当我们计算建造一个由 n 块砖组成的多层楼梯的方法数时，对于第一步 n-i，方法数是 - 用 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;
  }
}

动态规划解法讲解

Explanation of Dynamic Programming solution

java

algorithm

memoization

dynamic-programming