第十六关——动态规划

2020-05-04 11:02:59 下课铃虽晚，还好你步调慢，路虽长，想陪你都走完。——费启鸣《刘大志的歌》

五一匆匆过，就是不知半期何时来（不来最好），不过呢，我们还是要做好合适的动态规划。（最近还有一些比较纠结....的事情，那就好好做好动态规划吧）

这里附赠一个网站，有全套范围

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法

动态规划解题的一般思路：

1.将原问题分解成子问题，注意这个是否是一个独立的子问题，确定问题的最优解在子问题上也是最优的

2.确定状态，用状态把分解出来的问题尽可能定义出来

3.确定方程的边界状态，这是方程递推的基础，很多时候边界都会出问题

4.确定状态转移方程，考虑细致全面，不重复不遗漏，避免形成环状影响（DP的状态转移图是有拓扑序的），注意是否有后效性

2020-05-26 18:45:48 也许惦念好久的眷恋  不过一生中惊鸿一瞥——文橘《二三事》

•  01背包

题目描述：
给定 n 个物品和一个容量为 W 的背包，物品 i 的重量是 wi，其价值为 vi ，应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？（输出给定n和W时的最大总价值）

1、物品的顺序是固定的

同国王与金矿的问题一样，我们认为，物品的顺序是固定的，这样 才能够合理的写出最优子结构。

2、要考虑背包重量为0的情况（即使题目说了背包重量大于0）

我们假设F(n,w)代表物品为第n件结尾，背包空间为w时，所能够装下的最大价值。
那么，F(1,0)也是一定要存在的，表示只有一一个物品，但承重为0的情况！

因为在最优子结构中，可能会出现F(n-1,W-wi)+vi中，W-wi等于0的情况，此时前面的F(n,0)的值也应该为0，
此时，最有子结构的值就等于后面的被加数vi了。

因此，在构造一维数组时，需要初始化为res=[0]，再陆续添加重量为1,2，...，w的情况。（其实在国王与金矿构造的一维数组中，也需要考虑人数为0的情况的。）

3、构造数组时，要注意与重量列表中的重量一致

4、状态转移方程

• 当W-wi大于0时，F(n,w) = max(F(n-1,W-wi)+vi,F(n-1,w))

• 当W-wi小于0时，F(n,w) = F(n-1,w))

  先初始化一行，然后进行两个for循环，不断地滚动这两行，一直到最后的结果

博客详细

背包九讲

•  序列dp

状态设计思路：

1.既然是序列，那么一般都会有一个i表示做到第i项，如果是有两个序列，那么也会有一个j表示做到B序列的第j项，此时枚举是枚举下标的

2.如果题目给出k次机会之内的也要把状态记录下来，但是此时由于不知道什么时候用的机会，所以会类似定义发f[i][k]为用了k次机会，最后一次用在i身上，通常用来辅助转移g[i][k]表示用了k次机会，最后一次不一定用在i上

3.有些类似合并类的题目状态从前往后做无法表示，会设成f[i][j]表示第i项合并到第j项的代价，这时由于区间是不断拓宽的，只能先枚举区间的宽度再枚举左端点并确定右端点

4.对于一些大小为n的排列在规定条件下不同方案的问题，此时f[i][j]可以表示做到第i个，用了前j个数，最后一个用j。这时要把新来的i插进去，f[i-1]状态表示的排列很简单，如果最后一个数是k，把>=k的数全部加1就好，原本f[i-1]表示的排列在[1,i-1]内，>=k的数加了个1范围[1,i]

最长公共子序列（Least common Sequence）

给定两个字符串 s1 和 s2，求两个字符串的最长公共子序列。

子序列是一个字符串不连续的序列，如对于字符串  的一个子序列可以是 

那么，对于最长公共子序列，我们可以定义这样的一个状态 ，代表  (即 的前  个字符)和  最长公共子序列。需要注意到，上面的区间是前闭后开的。这样写的一个好处是，可以避免处理像 0 这样的边界。

那么，其对应的状态的转移方程可以表述如下：

2020-05-31 15:43:15 I'm the one you're my kryptonite——刘思鉴《在你身边就失去超能力》

•  线性dp

最长上升子序列问题

给定一个长度为N的的数列A，求数列单调递增的子序列长度最长是多少。

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

边界：f[0]=0 目标：max(f[i])

数字三角形

给定一个共有n行的三角矩阵A，其中第i行有j列。从左上角出发，每次可以向下方或右下方走一步，最终到达底部

if(j>1) f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1])

边界：f[1][1]=a[1][1] 目标 max(f[n][j])

• 区间dp

f[l][r] 表示一段连续区间 [l,r ] 上的答案

1序列: 区间 [l,r] 的最后一步处理的是 k 元素 / 分割点是 k / 受 k 控制的 常用四边形不等式优化

2环: 复制一下粘到后面, 枚举断点

3点集回路: 利用线段不交的性质按顺序 dp

• 期望dp

 概率Dp是一类求事件概率或期望的Dp的总称，对于求 概率问题，有时利用补集转化，或者将其转化为计数问题， 而对于求期望则大多利用期望的线性性来解决问题

• 环形dp

通常有两种解决办法：

1.执行两次dp。第一次在任意位置把欢断成链，按照线性来解，第二次再把链相连

2.把环断成链，然后复制一背在末尾。

题目大意：给定一个环上有n个数，分成m个部分，求这m个部分的和相乘的最大值和最小值。

f[i][j][k]表示在l到r中分成k段的最值

fmax[l][r][i]=max(fmax[l][r][i],fmax[l][k][i-1]*fmax[k+1][r][1])

fmin[l][r][i]=min(fmin[l][r][i],fmin[l][k][i-1]*fmin[k+1][r][1])

注意：环形dp要把数组开大一倍

•  树形dp

由于树有着天然的递归结构 父子结构 而且它作为一种特殊的图 可以描述许多复杂的信息 因此在树就成了一种很适合DP的框架
问题：给你一棵树 要求用最少的代价（最大的收益）完成给定的操作
树形DP 一般来说都是从叶子从而推出根 当然 从根推叶子的情况也有 不过很少
一般实现方式: DFS(包括记忆化搜索)，递推等

最大独立子集

最大独立子集的定义是，对于一个树形结构，所有的孩子和他们的父亲存在排斥，也就是如果选取了某个节点，那么会导致不能选取这个节点的所有孩子节点。
询问是让你给出这颗树的最大独立子集的大小。思路：对于任意一个节点，他都有两种选择：
A . 选择：A选择，那么他的孩子必定不能要，此时对于A和A的孩子们来说，能构成的最大独立子集是1+∑A.son.notcome。
B . 不选择：A不选择，那么他的孩子们可来可不来，此时对于A和A的孩子们来说，能构成的最大独立子集是
for i 1->son.size  father.notcome+=max(son.notcome,son.come);
当然可以在这基础上加以变化，比如给点设置权值，要你求得这个最大独立子集是满足有最大权值和的。

最优连通子集

Description
       众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示，如果x, y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，则称P1, P2相邻，记作P1~P2，否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集，即S = {P1, P2,..., Pn}(n >= 1)，其中Pi(1 <= i <= n)属于W，我们把S称为整点集。 定义 3 设S是一个整点集，若点R, T属于S，且存在一个有限的点序列Q1, Q2, ?, Qk满足: 1. Qi属于S（1 <= i <= k）; 2. Q1 = R, Qk = T; 3. Qi~Qi + 1(1 <= i <= k-1)，即Qi与Qi + 1相邻; 4. 对于任何1 <= i < j <= k有Qi ≠ Qj;
我们则称点R与点T在整点集S上连通，把点序列Q1, Q2,..., Qk称为整点集S中连接点R与点T的一条道路。 定义4 若整点集V满足：对于V中的任何两个整点，V中有且仅有一条连接这两点的道路，则V称为单整点集。 定义5 对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。
我们希望对于给定的一个单整点集V，求出一个V的最优连通子集B，满足： 1. B是V的子集 2. 对于B中的任何两个整点，在B中连通；
3. B是满足条件(1)和(2)的所有整点集中权和最大的。
Input
第1行是一个整数N（2 <= N <= 1000），表示单整点集V中点的个数；
以下N行中，第i行(1 <= i <= N)有三个整数，Xi, Yi, Ci依次表示第i个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。-10^6 <= Xi, Yi <= 10^6；-100 <= Ci <= 100。
Output
仅一个整数，表示所求最优连通集的权和。
Sample Input
5
0 0 -2
0 1 1
1 0 1
0 -1 1
-1 0 1
Sample Output
2
题目很繁琐，该题大意为：
给定一个平面整点集，点与点间在|x1-x2| + |y1-y2| = 1时相邻，且形成的图没有回路， 每个点有一个可正可负的权值，求最大权和连通子图.

/* 给定的是一颗树，根据题意，我们可以从任意一个节点出发，必能访问到其他所有节点，那么dp的起点可以在任意一个节点。 我们从该起点出发，对以此点为根的树的每个分支进行搜索，采用树的后续遍历法则，对于每个子树来说，dp值首先加上根节点 （因为要保证连通性，所以返回值中必须包含根节点的值，即使为负数也必须加上）先对每个分支dp，然后看分支dp的返回值是不是正数， 如果是正数，那么我们就把该分支的返回值加入到该树中去。 就是每个子树的根节点（包括叶子节点）记录dp[i][0]与dp[i][1]，前一个表示不包含根的最大值，后一个表示包含根的最大值。 那么我们可以得到对于dp[i][0]，必然是所有分支中dp[child][0]与dp[child][1]中大于0的最大值的累加 （因为不包含树根，所以在根节点上的连通性不用保证）, dp[i][1]必然是所有分支中dp[child][1]中大于0的最大值的累加再加上该树根本身的值（因为要保证连通性）。 最后只要比较dp[root][0]与dp[root][1]，输出较大。 */
#include <stdio.h>
#include <iostream>
using namespace std;
int Abs(int x) {
    return x>=0?x:-x;
}
int max(int x,int y,int z) {
    if(x<y) x=y;
    if(x<z) x=z;
    return x;
}
int max(int x,int y) {
    return x>y?x:y;
}
struct P {
    int x,y,c;
    void input() {
        scanf("%d%d%d",&x,&y,&c);
    } bool isConnect(P & t) {
        if(Abs(x-t.x)+Abs(y-t.y)==1) return 1;
        return 0;
    }
} p[1005];
struct Edge {
    int v,next;
} edge[10005];
int edgeNum,head[1005];
int dp[1005][2];
void addEdge(int u,int v) {
    edge[edgeNum].v=v;
    edge[edgeNum].next=head[u];
    head[u]=edgeNum++;
}
void dfs(int x,int father) {
    dp[x][0]=0;
    dp[x][1]=p[x].c;
    for(int i=head[x]; i!=-1; i=edge[i].next) {
        if(edge[i].v!=father) {
            dfs(edge[i].v,x);
            dp[x][0]=max(dp[x][0],dp[edge[i].v][0],dp[edge[i].v][1]);
            if(dp[edge[i].v][1]>0) {
                dp[x][1]+=dp[edge[i].v][1];
            }
        }
    }
}
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        for(int i=0; i<n; i++) {
            head[i]=-1;
            p[i].input();
        }
        edgeNum=0;
        for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) {
                if(p[i].isConnect(p[j])) {
                    addEdge(i,j);
                    addEdge(j,i);
                }
            }
        dfs(0,-1);
        printf("%d
",max(dp[0][0],dp[0][1]));
    }
}

//poj 1192 最优连通子集 (树型DP) /* 题意：给定一个平面整点集，点与点间在|x1-x2| + |y1-y2| = 1时相邻，且形成的图没有回路， 每个点有一个可正可负的权值，求最大权和连通子图。 题解：树型DP，dp[i][0]表示以i为根的子树上不包括i的最大权和，dp[i][1]表示包括i的最大权和。 */
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int inf = 1<<28;
int n,m;
struct Point {
    int x,y,c;
} p[1010];
vector<int> con[1010];
int dp[1010][2],mark[1010];
void dfs(int v) {
    mark[v]=1;
    dp[v][0]=0,dp[v][1]=p[v].c;
    int j;
    for (int i=0; i<con[v].size(); i++) if (!mark[con[v][i]]) {
            j=con[v][i];
            dfs(j);
            dp[v][0]=max(dp[v][0],max(dp[j][0],dp[j][1]));
            if (dp[j][1]>0) dp[v][1]+=dp[j][1];
        }
}
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
            if (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)==1) {
                con[i].push_back(j);
                con[j].push_back(i);
            }
    dfs(0);
    printf("%d/n",max(dp[0][0],dp[0][1]));
    return 0;
}

 优秀博客鉴赏

one.内容详细

two.类型讲解

three.图文介绍

four.轻松一刻