遞歸爬樓梯算法

我正在嘗試將下面的算法從遞歸更改爲迭代，並且遇到問題。（圖書：「破譯編碼訪談」）遞歸爬樓梯算法

問題：「一個孩子正在跑步樓梯，有n個步驟，一次可以跳1,2或3步。孩子可以通過很多方式跑上樓梯。「

本書的答案（遞歸）：

public static int countWays(int n, int[] map) { 

    if (n < 0) 
     return 0; 
    if (n == 0) 
     return 1; 
    if (map[n] > -1) 
     return map[n]; 

    map[n] = countWays(n - 1, map) + countWays(n - 2, map) + countWays(n - 3, map); 

    return map[n]; 

}

我的回答（迭代）：我與我給出的答案有

public static int countWays(int n, int[] map) { 

    for (int i = 1; i <= n; i++) { 

     //Problem with writing it this way: index could be negative 
     map[i] = map[i - 1] + map[i - 2] + map[i - 3]; 

    } 

    return map[n]; 

}

的一個問題是該行「地圖[我 - 1] + map [i - 2] + map [i - 3]「可能會導致負指數，這會導致錯誤。

我的代碼可能存在其他問題。

有人可以幫忙寫這個嗎？

來源

2015-07-22 randomUser47534

對於Python中的迭代O（n）和O（log（n））解決方案，請參見[本答案]（https://stackoverflow.com/a/40920969/832230）。 –

Hardcode第一個索引的值爲1，然後將總和的每個項置於其自己的if語句中以檢查負向索引。如果指數是負數，請不要將其包括在總和中。

或者，你可以硬編碼前三個值，然後從4開始，而不用擔心。

來源

2015-07-22 03:27:50 Aderis

-1

由於這顯然是一個編碼面試問題......我將向您展示一個類似的解決方案來回顧In Scala，以幫助您瞭解基本原理。

import scala.annotation.tailrec 

object Main { 

/** 
* Count ways to make change... 
*/ 
def countChange(money: Int, coins: List[Int]): Int = { 
    def reduce(money: Int, coins: List[Int]): Int ={ 
     if (money == 0) 1 
     else if (money < 0 || coins.isEmpty) 0 
     else reduce(money - coins.head, coins) + reduce(money, coins.tail) 
    } 
    reduce(money, coins) 
    } 
}

來源

2015-07-22 03:49:02

@Downvoter ...照顧評論？ –

public static int countWays(int n, int[] map) { 

    if(n == 0 || n==1) 
    return 1; 
    if(n == 2) 
    return 2; 
    map[0] = 1; 
    map[1] = 1; 
    map[2] = 2; 
    for (int i = 3; i <= n; i++) { 

     //Problem with writing it this way: index could be negative 
     map[i] = map[i - 1] + map[i - 2] + map[i - 3]; 

    } 

return map[n];

}

來源

2015-07-22 08:54:18

您正在使用被稱爲自底向上的動態規劃的迭代方法。這與自上而下的遞歸和遞歸不同。自下而上效率更高，因爲您避免了與遞歸相關的堆棧開銷。

Steps: 
1 -> 1 = 1 way 
2 -> 11, 2 = 2 ways 
3 -> 111, 12, 21, 3 = 4 ways 
4 -> 1111, 112, 121, 211, 22, 31, 31 = 7 ways

解決索引問題的另一種方法是創建一個最小大小爲3的數組，並從第3個索引開始。您正在使用更多空間，但它簡化了您的代碼。

public int countWaysDP(int n) { 
    if (n < 0) { 
     throw new IllegalArgumentException(); 
    } 
    int[] dp = new int[Math.max(3, n)]; 
    dp[0] = 1; // 1 
    dp[1] = 2; // 11, 2 
    dp[2] = 4; // 111, 12, 21, 3 
    for (int i = 3; i < n; i++) { 
     dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];  
    } 
    return dp[n - 1]; 
}

希望這有助於您的訓練。

來源

2016-03-17 04:41:54 ronn164

遞歸爬樓梯算法

回答

相關問題