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到n每個值2個遞歸調用，所以每次n增加一倍的呼叫總數。

動態規劃解決方案爲O(n)，因爲至多需要計算每n每個值爲n磚塊砌出樓梯的方法數量。

讀物

以下是有關動態規劃更多閱讀：https://en.wikipedia.org/wiki/Dynamic_programming

Answer 2

使用小型類來保存對（高度，磚），說：

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()方法從地圖返回。否則，請執行以下計算：

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;