作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试将以下算法从递归更改为迭代,但在这样做时遇到了问题。 (书籍:“破解编码面试”。)
问题:“一个 child 正在跑上 n 步楼梯,一次可以跳 1、2 或 3 步。实现一种方法来计算 child 可以跑上楼梯的方式。”
书的答案(递归):
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];
}
我给出的答案有一个问题是“map[i - 1] + map[i - 2] + map[i - 3]”行可能会导致负索引,这会引发错误。
我的代码可能还有其他问题。
有人可以帮忙写这个吗?
最佳答案
您使用的迭代方法称为自下而上的动态规划。它不同于带内存的自顶向下递归。自下而上效率更高,因为您避免了与递归相关的堆栈开销。
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];
}
希望这对你的训练有帮助。
关于java - 递归爬楼梯算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31553290/
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,
我是一名优秀的程序员,十分优秀!