【自顶向下】从一个规模较大的问题 f(20)，向下逐渐分解规模，直到 f(1)、f(2)触底，再逐层返回答案，这就是【自顶向下】

【自顶向上】直接从最低下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到想要的答案f(20)，这就是动态规划的思路。

---

求解动态规划的核⼼问题是穷举。

• 但是这类存在重叠子问题，直接暴力搜索效率较低。故需要一个备忘录或者DP Table，避免不必要的计算。

• 其一定具备最优子结构，才能通过子问题的最值得到原问题的最值。

• 由于问题千变万化，穷举所有可行解不不容易，故需要列出正确的状态转移方法。

重叠子问题，最优子结构，状态转移方程是动态规划的三要素。

写出状态转移方程一般是最难的，一个辅助框架：

明确 状态 -> 定义 dp数组/函数的含义 -> 明确 选择 -> 明确 base case。

摘自算法小抄

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。