如何记住递归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

总览

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

对于多次进行相同计算的递归解决方案，一种真正常见的优化模式是动态编程。这个想法是，与其多次进行相同的计算，我们只是在第一次执行时对每个计算进行缓存。然后每隔一段时间，如果我们需要计算完全相同的值，就可以从缓存中读取结果。

解

考虑到这一点，此解决方案应该有效。它使用与原始版本完全相同的逻辑，只是将递归步骤中的所有结果缓存在中，HashMap这样就永远不需要两次计算相同的东西。它还使用一个Staircase对象来跟踪（砖，高度）对。这是因为我们不能在中插入对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到的每个值进行2次递归调用n，因此每次n递增时，调用的总数就会增加一倍。

动态编程解决方案是O(n)因为最多需要n为的每个值计算一次用砖砌成楼梯的方法数量n。

附加阅读

以下是有关动态编程的更多信息：https :
//en.wikipedia.org/wiki/Dynamic_programming