初识DP

写在前面的话：

其实在去年寒假奥赛集训的时候，就已经接触DP了，但自己是真得对那时的自己很无语，不会,想不通，记不住就不管了，也没想过要一定把它吃透--但该来的总还是要来的。

所以现在就来玩好玩的DP吧。

DP分类：

一、简单基础dp

这类dp主要是一些状态比较容易表示，转移方程比较好想，问题比较基本常见的。主要包括递推、背包、LIS（最长递增序列），LCS（最长公共子序列）

二、区间dp

三、树形dp

四、数位dp

五、状态压缩dp

好，柿子先从软的捏

先了解dp的基本思想吧。

在现实生活中，有些过程可以分成若干个相互联系的阶段，在它的每一阶段都要做出决策，从而使整个过程达到最好的活动效果。其中，各个阶段决策的选取既依赖当前面临的状态，又影响以后的发展，当个各阶段决策确定后，就构成了一个决策序列。

动态规划问题满足三大重要性质

• 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
• 子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
• 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

 OK,现在就开始看第一个简单的模型吧--数字金字塔。

               
                 7
               3 8
              8 1 0
             2 7 4 4
            4 5 2 6 5

大体思想：

法1：顺推法

路径起点确定，中间点与终点相对不确定，定义f[x][y]为从（1，1）出发到达（x，y）的路径最大权值和。

因为要使从（x，y）到终点值最大，就要使（1，1）到（x，y）值最大，并且，到达（x，y）的路径就只有两条，一个左上，一个右上，当然，两边的点也不必担心，因为它的左上或右上的值为零，状态转移方程依然成立。

 f[x][y]=max{f[i-1][y-1],f[i-1][y]}+a[x][y]。

最后，ans为f[n][1~n]最大的一个

法2：逆推法（新颖的脑回路）

由顶向下分析，自底向上计算。

f[x][y]=max{f[x+1][y+1]+f[x+1][y]}+a[x][y]。

for(int i=1;i<=n;i++)

f[n][i]=a[n][i];

推荐博文;https://www.cnblogs.com/Renyi-Fan/p/9285495.html

and then  

LIS(最长上升子序列) 

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAX 110000
using namespace std;
int a[MAX],f[MAX];
int main()
{
 int n;
 cin>>n;
 for(int i=1 ; i<=n ; i++)
　　　cin>>a[i];
 for(int i=1 ; i<=n ; i++)
 {
  　f[i]=1;
  　for(int j=1;j<=n-1;j++)
  　　　if(a[i]>a[j]) f[i]=max(f[j]+1,f[i]);
 }
 sort(f+1,f+1+n);
 cout<<f[n];
 return 0;
 } 

以上为0（n^2)

我自己的理解：

f[i]表示以a[i]结尾的序列的最长长度，其序列最短也还是有一个的（本身），so初始化为f[i]=1；

后面如果有比a[i]小的，例如我们先设为a[k]吧，那我们可以选择将以a[i]结尾的那一串数接在a[k]的后面，此时以a[k]结尾的序列长度就为f[i]+1；

当然，选择这个a[i]接在后面不一定是最长的，所以我们要将目前已知f[i]的值与选择a[i]接在前面从而得到的值比较，

即 f[i]=max(f[j]+1,f[i])。

依次遍历a[1]~a[n],然后sort一下就能得到lis了。

有0（nlongn）的写法，但是，好吧，我不会啊。。。

LCS(最长公共子序列)：

 1 //T：最长公共子序列 
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 #define MAXN 2111
 6 
 7 using namespace std;
 8 
 9 int n, m;
10 int a[MAXN], b[MAXN];
11 int f[MAXN][MAXN];
12 int main() {
13     scanf("%d%d", &n, &m);
14     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
15     for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
16     
17     for(int i = 1; i <= n; i++) {
18         for(int j = 1; j <= m; j++) {
19             
20             f[i][j] = max(f[i - 1][j], f[i][j - 1]);
21             
22             if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
23             
24             else f[i][j] = max(f[i][j], f[i - 1][j - 1]);
25             
26         }
27     }
28     printf("%d\n", f[n][m]);
29     return 0;
30 }

OK,现在来看一些题目：（未完待续）

初识DP

原文：https://www.cnblogs.com/becase/p/11809013.html