sho*_*ory 7 algorithm recursion dynamic-programming
我是第一年本科CSc学生,他希望参加竞争性的编程.
递归涉及定义和解决子问题.据我了解,自顶向下动态编程(dp)涉及将子问题的解决方案记忆,以减少算法的时间复杂度.
可以自上而下使用dp来提高每个递归算法的效率和重叠子问题吗？dp在哪里无法工作,我该如何识别？
简短的回答是:是的.
但是,存在一些限制.最明显的一点是递归调用必须重叠.即在执行算法期间,必须使用相同的参数多次调用递归函数.这允许您通过memoization截断递归树.因此,您始终可以使用memoization来减少呼叫次数.
然而,这种电话的减少需要付出代价.您需要将结果存储在某处.下一个明显的限制是你需要有足够的内存.这带来了一个不太明显的约束.内存访问总是需要一些时间.您首先需要找到存储结果的位置,然后甚至可以将其复制到某个位置.所以在某些情况下,让递归计算结果而不是从某处加载它可能会更快.但这是特定于实现的,甚至可能取决于操作系统和硬件设置.