java - 如何内存递归 Java 方法？

Question

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

所以给定 N = 3你可以 build 一个楼梯:2 步，然后是 1 步

给定 N = 4你可以 build 一个楼梯:3 级台阶，然后是 1 级台阶

给定 N = 5您可以 build 两个楼梯: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

概览

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

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

解决方案

考虑到这一点，这个解决方案应该可行。它使用与您的原始版本完全相同的逻辑，它只是将递归步骤的所有结果缓存在 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