动态规划入门
本页面用到的网站：
洛谷：https://www.luogu.com.cn/
acwing：https://www.acwing.com/
引入：斐波那契数列
f[n]=1(n0||n1)
f[n]=f[n-1]+f[n-2] (n>1)
递归：
int f(int n){
if(n==1||n==0) return 1;
else return f(n-1)+f(n-2);
}
如图所示，太多问题被重复求了，所以我们引入一个概念：记忆化搜索
顾名思义，就是记住已经求过的问题，再次遇到时直接使用，所以上面的代码优化如下
int cal(int n){
if(f[n]) return f[n];
else return f[n]=cal(n-1)+cal(n-2);
}
此时，时间复杂度已经和递推一样都是O（n）了。
从数字三角形说起
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大
输入格式
第一个行一个正整数 $r$ ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 #1
30
【数据范围】
对于 $100%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。
大家第一眼应该可以看出可以暴力搜索，但是如果搜索时间复杂度很明显会超，我们仔细观察发现，从上向下走，走到每一格的最大值只和上面一格的最大值有关，并且走到每一格的最大值都会被多次用到多次（左下和右下都会用到），这就对应了你给他规划的三个基本性质
1.最优子结构，问题的最优解所包含的子问题的解也是最优的（走到每一格的最大值只和上面一格的最大值有关）
2.无后效性（走到每一格的最大值只和上面一格的最大值有关，和前面怎么走的无关）
3.子问题重叠性质（走到每一格的最大值都会被多次用到多次）
所以我们可以用一个二维数组保存走到每一个位置的最大值，核心递推式为：
f(i,j)=a(i,j)+max(f(i−1,j),f(i−1,j−1))
大家可以尝试一下写出这道题
简单递推
题目来源洛谷 P1002 过河卒（方案统计）
题目描述
棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 $B$ 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
样例 #1
样例输入 #1
6 6 3 3
样例输出 #1
6
对于 $100 %$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。
根据我们高中学的加法定理，我们移动一个点的方案数等于移动到（能移动到这个点的点）的方案数之和。（有点绕口）
我们先考虑没有马的情况。
这题每次只能向下或者向右，所以移动到每个点的方案数就等于（移动到上面的点的方案数）和（能移动到左边点的方案数）之和。那么我们设一个二维数组f表示移动到每个点的方案数，进行初始化，f[1][1]=1
接着进行我们刚才的递推即可
如果有马呢？
很简单，每个马能走到的位置和马本身的位置不进行计算或者转移，数值为0。
经典例题
题目来源洛谷 P1020 导弹拦截（ 最长上升子序列）
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例 #1
样例输入 #1
389 207 155 300 299 170 158 65
样例输出 #1
6
2
对于前 50%50% 数据（NOIP 原题数据），满足导弹的个数不超过 10^4104 个。该部分数据总分共 100100 分。可使用\mathcal O(n^2)O(n2) 做法通过。
对于后 50%50% 的数据，满足导弹的个数不超过 10^5105 个。该部分数据总分也为 100100 分。请使用 \mathcal O(n\log n)O(nlogn) 做法通过。对于全部数据，满足导弹的高度为正整数，且不超过 5\times 10^45×104。
Dilworth 定理：任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真。（感兴趣的可以了解，但是暂时不必深究，感性理解即可，在你们今后的离散数学课程中将学习相关知识）
根据该定理，本题求出给出数组的最长上升子序列长度即可。
很容易想到对于第i个数字来说，以第i个数字结尾的最长上升子序列一定是从前i-1个数字当中的最长上升子序列转移来的，所以以第i个数字结尾的最长上升子序列长度等于以第x（1<=x<=i-1）个数字结尾的最长上升子序列长度加一。
递推式：
//f[i]为以第i个数字结尾的最长上升子序列长度，a[i]为第i个数
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=1; j<i; j++) {
if(a[j]<a[i]) {
f[i]=max(f[i],f[j]+1);
}
}
ans=max(ans,f[i]);
}
本题满分两百，使用该方法可达到100分，如要达到200分，需使用二分或者数据结构优化寻找前i-1个数字当中的最长上升子序列长度的过程。
背包问题
01背包
题目来源 acwing#2：https://www.acwing.com/problem/content/solution/2/1/
题目描述
有 N 件物品和一个容量是 V 的背包。
每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
0<N,V≤1000
0<vi,wi≤1000
暴力：子集枚举，复杂度为 O（$2^n$）,显然无法通过
下面开始使用刚刚学到的动态规划思维思考
状态$f[i][j]$定义：前 i 个物品，背包容量 j 下的最优解（最大价值）：
当前的状态依赖于之前的状态，可以理解为从初始状态$f[0][0] = 0$开始决策，有 $N$ 件物品，则需要 $N$ 次判断，每一次对第 i 件物品的判断，状态f[i][j]不断由之前的状态更新而来。
第一种情况：当前背包容量不够$（j < v[i]）$，没得选，因此前 i个物品最优解即为前$i−1$ 个物品最优解：
对应代码：$f[i][j] = f[i - 1][j]$。
第二种情况：当前背包容量够，可以选，因此需要判断选与不选第 i 个物品：
选：$f[i][j] = f[i - 1][j - v[i]] + w[i]$。
不选：$f[i][j] = f[i - 1][j]$。
我们的决策是如何取到最大价值，因此以上两种情况取 max() 。
本题作为的最经典的例题，网上代码随处可见，但是希望理解的同学可以自己动手写出。
没有理解也没有关系，上课会借助画图讲解本题动态规划的实际过程，帮助理解。
完全背包
题目来源acwing#3：https://www.acwing.com/problem/content/3/
有 $N$ 种物品和一个容量是 $V$的背包，每种物品都有无限件可用。
第 $i$ 种物品的体积是 $vi$，价值是 $wi$。
求解将物品装入背包，使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
0<N,V≤1000
0<vi,wi≤1000
本题和01背包类似大家可以尝试独立思考，上课将会给出详细代码和讲解。
标签：背包,第七场,最大值,样例,导弹,JIT,寒假,物品,拦截 From： https://www.cnblogs.com/107557224-qyj/p/17030674.html