代码之家 › 专栏 › 技术社区 › John Down

动态三N步长

dynamic-programming recursion

John Down · 技术社区 · 8 年前

我正在解决破解编码面试的问题:

一个孩子跑上一个有n个台阶的楼梯,一次可以跳1步、2步或3步。实施一种方法来计算孩子可以跑上楼梯的可能方式。

def dynamic_prog(N):
    store_values = {1:1,2:2,3:3}
    return dynamic_prog_helper(N, store_values)

def dynamic_prog_helper(N, map_n):
    if N in map_n:
        return map_n[N]
    map_n[N] =  dynamic_prog_helper(N-1, map_n) + dynamic_prog_helper(N-2, map_n) + dynamic_prog_helper(N-3,map_n)
    return map_n[N]

我不知道为什么计算不正确。

dynamic_prog(5) = 11, but should be 13
dynamic_prog(4) =  6, but should be 7

1 回复 | 直到 8 年前

Prune 8 年前

关键问题是您的初始值 store_values[3] 4

2 1 1 2 1 1 1

def dynamic_prog(N):
    store_values = {1:1,2:2,3:4}
    return dynamic_prog_helper(N, store_values)
...
for stair_count in range(3, 6):
    print dynamic_prog(stair_count)

输出:

4
7
13

推荐文章

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

1 年前

MMedina · 将powershell应用于子文件夹

1 年前

YorSubs · Linux中遍历目录的时间不同方法[关闭]

1 年前

justiceorjustus · Javascript中异步递归函数块内部是否有同步函数调用?

1 年前

Puna · 这段代码如何执行finally块,即使它从未被评估为true?

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

Romn · 在递归函数中键入元组或元组列表

1 年前

David Alvarez · 高级打字脚本:查找嵌套对象中键“id”的所有值

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

Ack · 尝试迭代JSON数据以匹配用户输入

1 年前