如何记忆递归Java方法？ [英] How can a recursive Java method be memoized?
问题描述
所以我建立了这个程序来构建不同的楼梯案例。基本上问题是：给定一个整数N，你可以建立多少种不同的方法。 N保证大于3且小于200.任何前一步都不能大于其后续步骤，否则会违背楼梯的目的。
所以给出N = 3
你可以建造一个楼梯：2个步骤，然后是1个步骤
给定N = 4
你可以建造一个楼梯： 3步然后1步之后
给定N = 5
你可以建造两个楼梯：3步然后2步或4步然后1步。
我的方法如下，它的工作原理，除了它的运行时间太慢。所以我在考虑尝试对该方法进行memoization，但说实话，我并不完全理解如何实现它。如果我能得到一些帮助，那就是很棒。
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;
}
其他
{
返回砖块（高+1，brickLeft - 高度）+砖块（高+1，brickLeft）;
}
}
概述
所以你在这里有一个递归的解决方案。这适用于此类问题。在这个特定的递归解决方案中，您的递归步骤将使用相同的参数多次调用。
动态编程是递归解决方案的一种非常常见的优化模式，其中多次进行相同的计算。我们的想法是，我们不是多次进行相同的计算，而是在第一次执行时对每个计算进行缓存。然后每隔一次，如果我们需要计算完全相同的值，我们就可以从缓存中读取结果。
解决方案
考虑到这一点，这个解决方案应该有效。它使用与原始版本完全相同的逻辑，它只是缓存 HashMap 中递归步骤的所有结果，因此它永远不需要计算两次相同的事情。它还使用 Staircase 对象来跟踪（砖块，高度）对。这是因为我们不能将对插入 HashMap ，我们只能插入单个对象。
只需更改变量砖到你想要解决的任何价值。
公共类楼梯{
private static HashMap< Staircase，Integer>缓存;
public static void main（String [] args）{
cache = new HashMap<>（）;
int bricks = 6;
Staircase toBuild = new Staircase（1，brick）;
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;
}否则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）;
返回返回;
}
@Override
public boolean equals（Object other）{
if（other instanceof Staircase）{
if（height！=（（Staircase） ）其他）。高度）{
返回false;
}
if（bricksLeft！=（（Staircase）other）.bricksLeft）{
return false;
}
返回true;
}
返回false;
}
@Override
public int hashCode（）{
int hash = 5;
hash = 73 * hash + this.height;
hash = 73 * hash + this.bricksLeft;
返回哈希值;
}
}
分析
我测试了它，性能比你以前的版本快得多。它立即计算最多200个值。
您的原始函数是 O（2 ^ n）。这是因为我们为 1 到 n 的每个值进行了2次递归调用，因此调用总数翻了一番每次n增加。
动态编程解决方案是 O（n）因为它最多需要为 n 的每个值计算一次从 n 砖中制作楼梯的方法数。
补充阅读
So given N = 3 You can build one staircase: 2 steps and then 1 step following that
Given N = 4 You can build one staircase: 3 steps and then 1 step following that
Given N = 5 You can build two staircases: 3 steps and then 2 steps OR 4 steps and then 1 step.
My method is below and it works, except its runtime is far too slow. So I was thinking of trying to make a memoization for the method, but to be honest I do not fully understand how to implement this. If I could get some help on how to do so that'd be great.
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);
}
}
Overview
So what you have here is a recursive solution. That works well for this type of problem. In this particular recursive solution, your recursive step will be called with the same arguments many times.
One really common optimization pattern for recursive solutions where the same calculation is being made many times is Dynamic Programming. The idea is that instead of doing the same calculation many times, we just cache each calculation the first time we do it. Then every following time, if we need to calculate the exact same value, we can just read the result from the cache.
Solution
With that in mind, this solution should work. It uses exactly the same logic as your original version, it just caches all results for the recursive step in a HashMap so that it never needs to calculate the same thing twice. It also uses a Staircase object to track pairs of (bricks, height). This is because we cannot insert pairs into a HashMap, we can only insert single objects.
Just change the variable bricks to whatever value you want to solve for.
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;
}
}
Analysis
I tested it out and the performance is much faster than your previous version. It computes values up to 200 instantly.
Your original function was O(2^n). That is because we make 2 recursive calls for each value from 1 to n, so the total number of calls is doubled for each time n is incremented.
The Dynamic Programming solution is O(n) since at most it will need to calculate the number of ways to make a staircase out of n bricks once for each value of n.
Additional Reading
Here is some more reading about Dynamic Programming: https://en.wikipedia.org/wiki/Dynamic_programming
这篇关于如何记忆递归Java方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
