动态规划往往是最能有效考察算法和设计能力的题目类型,面对这类题目最重要的是抓住问题的阶段,了解每个阶段的状态,从而分析阶段之间的关系转化。

适用于动态规划的问题,需要满足最优子结构和无后效性,动态规划的求解过程,在于找到状态转移方程,进行自底向上的求解。

自底向上的求解,可以帮你省略大量的复杂计算,例如上面的斐波拉契数列,使用递归的话时间复杂度会呈指数型增长,而动态规划则让此算法的时间复杂度保持在O(n)

# 路径问题

# 买卖股票类问题

# 子序列问题