在计算它的最终答案的过程中解决N个子问题的任何动态编程算法必须在Ω（N）时间内运行。
这个陈述是真的吗？我认为这确实是正确的，因为我需要计算每个子问题。如果我错了，请告诉我
最简洁的答案是不。与实际算法相比，动态编程更像是提升性能/缩短运行时复杂性的策略。在不知道特定问题的实际算法的情况下，不可能对时间复杂性做任何说明。
DP的想法是使用memoization（通过消耗一些空间）来加速现有算法。此外，您可以应用DP的每个算法都可以以不同的方式加速。如果不重新计算多次相同的子任务，则必须将中间结果存储在另一个数据结构中。如果在数据结构中再次需要结果，则将直接返回已存储的中间结果
话虽如此，DP问题的时间复杂性是每个状态所需的唯一状态/子问题*的数量。
这是DP解决N个子问题并且计算不是Ω（N）的一个例子。让我们假设你的DP需要O（n）个子问题，并且评估每个子问题需要花费O（logn）二元搜索和恒定时间操作。
然后整个算法将采用O（n * logn）。