-
跳台阶问题
-
背包问题
-
“最长”问题
- 最长公共子序列问题 -- 求两个字符串最长连续公共序列，查找最长子串
- 最长递增子序列问题
- 最长回文子串问题
-
小白兔棋盘（卡特兰数）问题
-
硬币找零问题
-
有很多个2毛硬币，3毛硬币，5毛硬币，现在问你组成x毛的硬币的方案数
-
有 2,3,7 面值，取100元。（动态规划）
-
**递归算法是一种直接或者间接调用自身函数或者方法的算法。**递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：
-
- 一个问题的解可以分解为几个子问题的解
-
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
-
- 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口
回溯：穷举。一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View)
贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边
动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)。
将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
-
最优子结构
-
边界
-
状态转移方程
-
什么样的问题可以用动态规划解决？
-
解决动态规划问题的一般思考过程是什么样的？
-
贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？
什么样的问题适于用动态规划解决？
“一个模型三个特征”
- 最优子结构
- 无后效性
- 重叠子问题
动态规划解题思路：
-
状态转移表法
-
状态转移方程法
根据最优子结构，写出状态转移方程，比如在「 爬台阶问题 」中
f(10) = f(9) + f(8)是【最优子结构】
f(1) 与 f(2)是【边界】
f(n) = f(n-1) + f(n-2)【状态转移公式】
递归
Fib(n) = Fib(n-1) + Fib(n-2)
大多数动态规划问题本质都是递归问题。但是重叠子问题会导致递归算法性能比较差。解决办法：
- 记忆化搜索 - 自上而下的解决问题
- 动态规划 - 自下而上的解决问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：2 示例 2：
输入：n = 7 输出：21 示例 3：
输入：n = 0 输出：1 提示：
0 <= n <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
实现：
背包容量为C（Capacity），现在有n种不同的物品，编号0...n-1，其中每一件物品的重量为w(i)，价值为v(i)。问可以向这个背包中盛放哪些物品，使得总价值最大。
贪心算法：挑最大的放，可能导致背包中最后剩空间，浪费了。
F(n , C) = F(i -1 ,c)
=v(i) +F(i -1, c - w(i))
目的是取最大
得出状态转移方程
F(i , c) = max(F(i -1 ,c), v(i) + F(i -1 ,c - w(i)))
找出 s 中最长的回文子串。你可以假设 s 的最大长度为 1000