算法知识结构梳理

数组

链表

栈

队列

散列表

树

递归

分治

回溯

动态规划

定义

• simplifying a complicated problem by breaking it down into simper problems(in a recursive manner)
• Divide & Conquer + Optimal substructure (分治+最优子结构)

思想与应用

• 思想上，若要解一个给定的问题，我们需要解其不同部分(即子问题)，再根据子问题解以得出问题的解
• 动态规划常常适用于有重叠子问题和最有子结构性质的问题

解题关键点

• 动态规划和递归或者分治没有根本上的区别(关键看有无最优子结构)
• 共性: 找到重复子问题
• 差异性：最优子结构、中途可以淘汰次优解

题目

• 509. 斐波那契数 ☑️

贪心

查找

排序