DP(动态规划)
动态规划（Dynamic Programming，DP），简称动规，或DP，是运筹学的一个分支，是求解决策过程最优化的过程。其思想是将一个问题分解为若干个子问题，对每个子问题求最优解，前一个子问题的最优解，为下面的子问题提供了有效信息，依次解决子问题，最后一个子问题就是初始问题的最优解。动态规划应用于子问题重叠的情况，子问题的划分是通过递归实现。为了避免子问题的重复计算，保证每个子问题只求解一次，会将解保存在数组中。
动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，蓝桥杯ACM等竞赛当中，广泛在背包问题、生产经营、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性等问题背景中使用，是算法竞赛中的份量极高的算法之一
相关题目
相关文章
| 序号 | 标题 |
|---|---|
| 1 | 动态规划DP算法详解 |
| 2 | 什么是动态规划? |
| 3 | 动态规划概念和实例讲解 |
| 4 | 什么是记忆化搜索？ |
| 5 | 记忆化搜索实例讲解 |
| 6 | 超详细背包DP九讲（算法分析+问题分析+代码分析） |
| 7 | 区间DP实例讲解 |
| 8 | DAG上的DP实例讲解 |
| 9 | 树形DP概念和实例讲解 |
| 10 | 数位DP概念和实例讲解 |
| 11 | 什么是状态压缩DP？ |
| 12 | 状态压缩DP图文实例讲解（一） |
| 13 | 状态压缩DP图文实例讲解（二） |
| 14 | 什么是哈希？ |
| 15 | 插头DP图文实例讲解 |
| 16 | 计数DP实例讲解 |
| 17 | 什么是概率DP？ |
| 18 | 概率DP实例讲解 |
| 19 | 什么是线性DP? |
| 20 | 线性DP图文实例讲解 |
| 21 | 动态DP实例讲解 |
| 22 | DP优化（一）单调队列/单调栈优化实例讲解 |
| 23 | DP优化（二）斜率优化实例讲解 |
| 24 | DP优化（三）四边形不等式优化实例讲解 |
| 题号 | 标题 | 解决/提交 | ||
|---|---|---|---|---|
| 2474 | 信息学奥赛一本通T1569-石子合并 | 中等题 | 78/233 | |
| 2475 | 信息学奥赛一本通T1570-能量项链 | 中等题 | 38/108 | |
| 2476 | 信息学奥赛一本通T1571-凸多边形的划分 | 中等题 | 34/90 | |
| 2477 | 信息学奥赛一本通T1572-括号配对 | 中等题 | 20/59 | |
| 2478 | 信息学奥赛一本通T1573-分离与合体 | 中等题 | 5/6 | |
| 2479 | 信息学奥赛一本通T1574-矩阵取数游戏 | 中等题 | 9/28 | |
| 2480 | 信息学奥赛一本通T1575-二叉苹果树 | 中等题 | 33/55 | |
| 2481 | 信息学奥赛一本通T1576-选课 | 中等题 | 13/18 | |
| 2482 | 信息学奥赛一本通T1577-数字转换 | 中等题 | 33/55 | |
| 2483 | 信息学奥赛一本通T1578-战略游戏 | 中等题 | 17/35 | |
| 2484 | 信息学奥赛一本通T1579-皇宫看守 | 中等题 | 38/85 | |
| 2485 | 信息学奥赛一本通T1580-加分二叉树 | 中等题 | 9/11 | |
| 2486 | 信息学奥赛一本通T1581-旅游规划 | 中等题 | 12/39 | |
| 2487 | 信息学奥赛一本通T1582-周年纪念晚会 | 中等题 | 6/15 | |
| 2488 | 信息学奥赛一本通T1583-叶子的染色 | 中等题 | 4/5 | |
| 2489 | 信息学奥赛一本通T1585-Amount of Degrees | 中等题 | 15/31 | |
| 2490 | 信息学奥赛一本通T1586-数字游戏 | 中等题 | 33/79 | |
| 2491 | 信息学奥赛一本通T1587-Windy 数 | 中等题 | 29/50 | |
| 2492 | 信息学奥赛一本通T1588-数字游戏 | 中等题 | 22/90 | |
| 2493 | 信息学奥赛一本通T1589-不要 62 | 中等题 | 36/141 | |
| 2494 | 信息学奥赛一本通T1590-恨 7 不成妻 | 中等题 | 4/16 | |
| 2495 | 信息学奥赛一本通T1592-国王 | 中等题 | 38/128 | |
| 2496 | 信息学奥赛一本通T1593-牧场的安排 | 中等题 | 5/6 | |
| 2497 | 信息学奥赛一本通T1594-涂抹果酱 | 中等题 | 8/16 | |
| 2498 | 信息学奥赛一本通T1595-炮兵阵地 | 中等题 | 11/18 |