如何记忆递归 Java 方法？

Question

所以我构建了这个程序来构建不同的楼梯案例。本质上的问题是：给定一个整数 N，你可以用多少种不同的方式建造楼梯。 N 保证大于 3 且小于 200。任何前一步都不能大于其后一步，否则它会破坏楼梯的目的。

所以给定 N = 3 您可以建造一个楼梯：2 步，然后是 1 步

给定 N = 4 您可以建造一个楼梯：3 步，然后是 1 步

给定 N = 5 您可以建造两个楼梯：3 级台阶然后 2 级台阶或 4 级台阶然后 1 级台阶。

我的方法在下面并且有效，只是它的运行时间太慢了。所以我在考虑尝试为该方法做一个记忆，但老实说我不完全理解如何实现它。如果我能得到一些关于如何这样做的帮助，那就太好了。

public static void main(String [] args)
{
    System.out.println(answer(200));
}
public static int answer(int n) { 
    return bricks(1,n) -1;
}
public static int bricks(int height, int bricksLeft)
{
    if(bricksLeft == 0)
    {
        return 1;
    }
    else if(bricksLeft < height)
    {
        return 0;
    }
    else
    {
        return bricks(height +1, bricksLeft - height) + bricks(height +1, bricksLeft);
    }
}

Answer 1

用小的class装对子（身高，砖头），说：

private static class Stairs {
    private int height;
    private int bricks;
    Stairs(int height, int bricks) {
        this.height = height; this.bricks = bricks;
    }
}

然后使用一个全局的HashMap<Stairs, Integer>，初始化在main():

map = new HashMap<Stairs, Integer>();

在 bricks() 函数中，检查特定（高度、砖块）对的解决方案是否在地图中。如果是，只需通过调用 get() 方法从地图中 return 它。否则，进行计算：

Stairs stairsObj = new Stairs(height, bricks);
if(map.get(stairsObj) == null) {
    // Put your compute code here
}

在函数中的每个 return 语句之前，添加两个额外的语句。类似于：

int result = <whatever you are returning right now>;
map.put(stairsObj, result);
return result;

Answer 2

概览

所以你这里有一个递归解决方案。这适用于此类问题。在这个特定的递归解决方案中，您的递归步骤将使用相同的参数多次调用。

对于多次进行相同计算的递归解决方案，一种真正常见的优化模式是动态规划。我们的想法是，我们不是多次执行相同的计算，而是在第一次执行时缓存每个计算。然后每次以后，如果我们需要计算完全相同的值，我们可以直接从缓存中读取结果。

解决方案

考虑到这一点，此解决方案应该可行。它使用与原始版本完全相同的逻辑，它只是将递归步骤的所有结果缓存在 HashMap 中，因此它永远不需要计算相同的东西两次。它还使用 Staircase 对象来跟踪成对的 (bricks, height)。这是因为我们不能将对插入HashMap，我们只能插入单个对象。

只需将变量 bricks 更改为您想要求解的任何值。

public class Staircase {

    private static HashMap<Staircase, Integer> cache;

    public static void main(String[] args) {
        cache = new HashMap<>();
        int bricks = 6;
        Staircase toBuild = new Staircase(1, bricks);
        System.out.println(toBuild.waysToBuild() - 1);
    }

    public final int height;
    public final int bricksLeft;

    public Staircase(int height, int bricksLeft) {
        this.height = height;
        this.bricksLeft = bricksLeft;
    }

    public int waysToBuild() {
        if (cache.containsKey(this)) {
            return cache.get(this);
        }

        int toReturn;
        if (bricksLeft == 0) {
            toReturn = 1;
        } else if (bricksLeft < height) {
            toReturn = 0;
        } else {
            Staircase component1 = new Staircase(height + 1, bricksLeft - height);
            Staircase component2 = new Staircase(height + 1, bricksLeft);
            toReturn = component1.waysToBuild() + component2.waysToBuild();
        }

        cache.put(this, toReturn);
        return toReturn;
    }

    @Override
    public boolean equals(Object other) {
        if (other instanceof Staircase) {
            if (height != ((Staircase) other).height) {
                return false;
            }
            if (bricksLeft != ((Staircase) other).bricksLeft) {
                return false;
            }
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 73 * hash + this.height;
        hash = 73 * hash + this.bricksLeft;
        return hash;
    }
}

分析

我测试了一下，性能比你以前的版本快多了。它立即计算最多 200 个值。

您的原始函数是 O(2^n)。这是因为我们对从 1 到 n 的每个值进行了 2 次递归调用，因此每次递增 n 时，调用总数都会加倍。

动态规划的解决方案是O(n)，因为它最多需要为n的每个值计算一次用n块砖制作楼梯的方法数。

补充阅读

这里有一些关于动态规划的更多阅读：https://en.wikipedia.org/wiki/Dynamic_programming

如何记忆递归 Java 方法？

How can a recursive Java method be memoized?

java

recursion

dynamic-programming

memoization