无显式结构的动态规划：数列第n项问题

摘要: 动态规划解决数列第 n 项问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$$\{a_{n}\}$$

在组合数学中，在很多与数列 $\{a_{n}\}$ 相关的问题：给定初始值 $a_{0}, a_{1},\cdots$ 以及一些规则，问 $\{a_{n}\}$ 的值。

如果我们把 $n = 0, 1, 2, \cdots$ 时数列的值 $dp[i]$ 视为一个个状态，基于给定规则写出状态转移方程，就可以用动态规划的方式解决。

这种问题不像通常的线性动态规划那样有一个显式的数组或字符串这样的线性结构，而是由数列的下标隐含一个线性结构。状态转移并不一定是线性的，根据递推的规则，状态也可能时按照拓扑序转移的。

这种没有显式串，有一定数学背景的问题，通常还可以用数学的方式推出 $a_{n}$ 的表达式，这样可以求 $n$ 很大时的值。本文汇总了若干个这样的题目。

---

650. 只有两个键的键盘

• 题解参考：通过不等式解决的算法问题。
• 数学背景：数论、不等式

---

651. 4键键盘

• 题解参考：剪枝优化DP：基于数学性质排除大量无效决策。
• 数学背景：不等式

---

264. 丑数 II

• 题解参考：决策单调性：决策候选集随状态推导递增而目标函数不变。
• 数学背景：不等式

---

279. 完全平方数

• 题解参考：在DP状态转移的DAG上BFS：从动态规划的角度理解权图最短路径。
• 数学背景：数论

---

343. 整数拆分/剑指 Offer 14- I. 剪绳子

• 题解参考：使得乘积最大的整数分拆：基于数学性质对决策空间剪枝。
• 数学背景：不等式

---

920. 播放列表的数量

• 这是一个二元数列 $\{a_{n, m}\}$ 的例子
• 题解参考：排列计数：基于初等计数原理与容斥原理设计状态表示。
• 数学背景：组合数学

---

887. 鸡蛋掉落

• 这是二元数列的例子；
• 题解参考：单峰性与二分优化DP：鸡蛋掉落/求解差分方程/函数方程优化DP：N个鸡蛋掉落问题
• 数学背景：分析、优化、方程、组合数学

---

1884. 鸡蛋掉落-两枚鸡蛋

• 题解参考：两枚鸡蛋的鸡蛋掉落：单峰性、决策单调性、差分方程
• 数学背景：分析、优化、方程、组合数学

---