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

概述

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

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

解决方案

考虑到这一点，这个解决方案应该可行。它使用与原始版本完全相同的逻辑，它只是将递归步骤的所有结果缓存在 a 中，HashMap这样它就不需要两次计算相同的结果。它还使用一个Staircase对象来跟踪成对的（砖块、高度）。这是因为我们不能将对插入到 a 中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)最多需要计算一次用砖砌楼梯的方法数。nn

补充阅读

以下是有关动态编程的更多阅读内容： https: //en.wikipedia.org/wiki/Dynamic_programming