基本概念
最近在刷牛客编程题的时候，遇到了动态规划，借此机会更个博客写写动态规划。一句话总结：动态规划算法通常用于求解具有最优性质的问题。《算法导论》第三版解释如下：动态规划（dynamic planning）与分治法相思，都是通过组合子问题的解来求原问题（在这里，”programming”指的是一种表格法，并非编写的计算机程序）。……分治法将问题划分为互不相干的子问题，递归地求解子问题，再将他们的解组合起来，求出原问题的解。与之相反的，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治法会做许多不必要的工作，它会反复地求解那些公共的子子问题。动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。
动态规划的算法设计思路
动态规划的难点在于从一个抽象的问题中总结出动态规划表dp，dp一般是一个一维数组，也可能是多维数组或其他数据结构。求解问题的时候，要思考这个问题到底是怎么行动的，即算法运行的步骤。一般分析这三个步骤：
- （1）问题到
哪个阶段 - （2）问题的
状态 - （3）
从前一个状态到后一个状态的递推关系
举例说明
1.拦截导弹
A国有一套导弹防御系统，在敌国向国内发射导弹时，该系统回依次发射拦截弹，将飞来的导弹拦截下来。但是这个系统有一个缺陷，它的第n+1发拦截弹会比第n发拦截弹的高度要低。假设此时敌国发射来N发导弹，高度不一，那么一套拦截系统，最多可以拦截多少枚导弹？
- 问题实质：寻找最长递减子序列
- 假设N枚导弹飞来次序与高度H[1-8]如下：334，204，150，300，212，156，135，86。
- 解析:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
原问题：最多拦截多少枚导弹
子问题：从第1枚导弹开始，到第t枚导弹之间，最多能拦截多少枚导弹
子子问题：从第t枚导弹开始，到最后一枚导弹，最多能拦截多少枚导弹。
1.从最后一个高度开始。H[8] = 86，后面高度为空，所以没有导弹比H[8]高。记录状态表dp[8] = 1，表示从第8个导弹开始（包含第8个）开始拦截，只有1个导弹能被拦截。
2.再看H[7]，高度H[7] = 135 > H[8]，说明H[7]能被拦截到。记录状态表dp[7] = 1 + dp[8] = 2，表示从第7个（包含第7个）开始拦截，只有2个导弹能被拦截。
3.我们再看H[6]，H[6] = 156 > H[7]，说明H[6]能被拦截到。记录状态表dp[6] = 1 + dp[7] = 3，表示从第6个（包含第6个）开始拦截，只有3个导弹能被拦截到。
4.我们再观察H[5]，同理记录dp[5] = 1 + dp[6] = 4；
5.同理H[4] > H[5],记录状态表dp[4] = 1 + dp[5] = 5；
6.我们再看H[3]，发现H[3] < H[4],但是大于H[7],所以记录表可以写成dp[3] = 1 + dp[7] = 3；表示如果一开始就拦截第三枚导弹，则只能拦截到3个导弹。
7.同理dp[2] = 1 + dp[3] = 4，表示如果一开始就拦截第2枚导弹，则最多只能拦截4枚导弹。
8.dp[1] = 1 + dp[2] = 5;表示如果一开始就拦截第1枚导弹，则最多只能拦截5枚导弹。
* 其中dp最大的数目就是最多可以拦截的导弹数目。
- 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
int main()
{
vector<int> missile = {334,204,150,300,212,156,135,86};
int len =missile.size();
vector<int> dp(len);
for(int i = 0;i < len;i++){
dp[i] = 0;
}
for (int i = len - 1; i >= 0;i--)
{
int max = 0;
int cur = i;
for(int j = i + 1;j < len;j++)
{
if(missile[j] > missile[j + 1]&&)
}
}
return 0;
}
