动态规划(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优化(三)四边形不等式优化实例讲解 |
题号 | 标题 | 解决/提交 | ||
---|---|---|---|---|
3056 | 宠物小精灵之收服 | 入门题 | 44/84 | |
3057 | 买书 | 入门题 | 67/119 | |
3058 | Charm Bracelet | 入门题 | 32/98 | |
3059 | 开餐馆 | 入门题 | 41/113 | |
3060 | 合并石子 | 入门题 | 58/110 | |
3061 | 公共子序列 | 入门题 | 78/153 | |
3062 | 计算字符串距离 | 入门题 | 42/86 | |
3063 | 糖果 | 入门题 | 25/88 | |
3064 | 鸡蛋的硬度 | 入门题 | 30/47 | |
3065 | 最长公共子上升序列 | 入门题 | 23/112 | |
3066 | Maximum sum | 入门题 | 29/55 | |
3067 | 大盗阿福 | 入门题 | 210/547 | |
3068 | 股票买卖 | 入门题 | 49/143 | |
3069 | 鸣人的影分身 | 入门题 | 47/100 |