递归爬楼梯算法

我正在尝试将下面的算法从递归更改为迭代，并且遇到问题。（图书：“破译编码访谈”）递归爬楼梯算法

问题：“一个孩子正在跑步楼梯，有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

递归爬楼梯算法

回答

相关问题