动态规划dp

dp

线性dp

最长上升子序列 I ($O(n^2)$)

求数值严格单调递增的子序列的长度最长是多少?

状态：$f[i]$ 表示 i 位置记录的严格单调递增的子序列的最大长度

for( int i = 1; i <= n; i ++ ){
    f[i] = 1; // 每个数最小长度为 1
    for( int j = 1; j < i; j ++ ){ 
        if(arr[j] < arr[i]){ 
        // 遍历 i 位置前的数，比 i 位置小的数的位置 j 的严格单调递增的子序列的最大长度 + 1
            f[i] = max(f[i], f[j] + 1);
            // 状态转移 取max
        }
    }
    res = max(f[i], res);
}

最长上升子序列 II ($nlogn$)

思路：首先数组arr中存输入的数（原本的数），开辟一个数组f用来存结果，最终数组f的长度就是最终的答案；假如数组f现在存了数，当到了数组a的第i个位置时，首先判断$arr[i] > f[cnt]$ ？ 若是大于则直接将这个数添加到数组f中，即$f[++cnt] = arr[i]$;这个操作时显然的。
当$arr[i] <= f[cnt]$ 的时,我们就用$arr[i]$去替代数组f中的第一个大于等于$a[i]$的数，因为在整个过程中我们维护的数组f 是一个递增的数组，所以我们可以用二分查找在 $logn$ 的时间复杂的的情况下直接找到对应的位置，然后替换，即 $f[l] = arr[i]$。

int len = 0, res = 0;
for( int i = 1; i <= n; i ++ ){
    int l = 0, r = len;
    while(l < r){//二分查找最大小于 arr[i] 数的位置 r
        int mid = l + r + 1 >> 1;
        if(q[mid] < arr[i]) l = mid;
        else r = mid - 1;
    }
    len = max(len, r + 1);//替换长度不变，添加 len = r + 1
    q[r + 1] = arr[i]; //替换或添加
}

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

4 5
acbd
abedc

3

状态： $f[i][j]$ 表示以 $a[i],b[j]$ 结尾的字符的最长公共子序列最大长度

• 00 表示以 $a[i],b[j]$ 结尾的字符都不在最长公共子序列中
• 01 表示 $a[i]$ 不在, $b[j]$ 在
• 10 表示 $a[i]$ 在, $b[j]$ 不在
• 11 表示 $a[i],b[j]$ 都在，但 $a[i] == b[j]$

for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= m; j ++ ){
        if(s[i] == t[j])f[i][j] = f[i - 1][j - 1] + 1; 
        // 第四种状态 最长公共子序列长度 + 1
        else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        // 其他状态表示 00 包含在 01 或 10 中
    }
}

编辑距离

题目：编辑距离

状态： $f[i][j]$ 表示以 $a[i]$ 变成 $b[j]$ 的最少操作次数

• 删除: 删除$a[i]$ 使 $a[i - 1] = b[j]$： $f[i - 1][j] + 1$
• 添加: 在 $a[i]$ 后面添加 $b[j]$ 使 $a[i + 1] = b[j]$： $f[i][j - 1] + 1$
• 替换： 当$s[i] = t[j]，f[i - 1][j - 1]$ 否则$f[i - 1][j - 1] + 1$

for(int i = 0; i <= n; i ++ )f[i][0] = i; //删除所有a[i]
for(int i = 0; i <= m; i ++ )f[0][i] = i; //添加所有b[j]

for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= m; j ++ ){
        f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); 
        if(s[i] == t[j])f[i][j] = min(f[i][j], f[i - 1][j - 1]);
        else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
    }
}

区间dp

所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j自动获得，j = i + len - 1）

石子合并

题目：石子合并

状态：$f[i][j]$ 表示区间 i 到 j 的合并的最小代价

1. $i < j$ 时，$f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] − s[i − 1])$

2. $i = j$ 时， $f[i][i] = 0$（合并一堆石子代价为 0）

通过区间 2 ~ n 划分，找出所有相邻两堆石子的最小质量

for(int i = 1;i <= n; i++) s[i] += s[i - 1] + arr[i];//前缀和，找出区间总和
for(int len = 2; len <= n; len ++){//划分区间大小
        for(int i = 1; i + len - 1 <= n; i ++){
            int l = i,r = i + len - 1;//划分左端点，右端点
            f[l][r] = 1e8;//找最小，初始化区间总和为无穷
            for(int k = l; k < r; k ++){// k 为 两个区间分界点
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

树形dp

没有上司的舞会

题目：没有上司的舞会

题意：员工不能不能和直接上司一起参加晚会

思路：通过树建立关系，从根结点dfs开始遍历所有子结点

状态：$f[i][j]$ 表示 i 结点, j 选取或不选取

• 选取根结点： $f[u][1]$ 则其儿子结点不能再选
• 不选根节点： $f[u][0]$ 则只能选取儿子结点中的最大值

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 6010;
int f[N][2];
int e[N], ne[N], w[N], h[N], idx;
bool has_father[N];
int n;
void add(int a, int b){//链式前向星建树
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    f[u][1] = w[u]; //赋予根结点权值
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        dfs(j);//dfs从根结点开始遍历子结点
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];//两种状态选取
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )cin >> w[i];
    for (int i = 1; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        add(b , a);// 建树
        has_father[a] = true; //确认 a 有父节点
    }
    int root = 1;
    while(has_father[root])root ++;//寻找根结点
    dfs(root);
    
    cout << max(f[root][0], f[root][1]) <<endl; 
}

状态压缩dp

蒙德里安的梦想

题目：蒙德里安的梦想

思路：摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。

状态：f[i][j]
表示已经将前 i - 1 列摆好，且从第 i − 1 列，伸出到第 i 列的状态是 j 的所有方案。其中 j 是一个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致。

#include <bits/stdc++.h>
using namespace std;

const int N = 12, M = 1<< N;  

long long f[N][M] ;// 第一维表示列， 第二维表示所有可能的状态

bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //两种写法等价:二维数组

int m, n;

int main() {

    while (cin >> n >> m, n || m) { //读入n和m，并且不是两个0即合法输入就继续读入

        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0

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

            int cnt = 0 ;//记录连续的0的个数

            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true

            for(int j = 0; j < n; j ++) { //遍历这一列，从上到下

                 if ( (i >> j) & 1) {  
                     //i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                     // &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) { 
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid =false; break;
                    } 

                    cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    //其实清不清零没有影响
                 }
                 else cnt ++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1)  isValid = false; //最下面的那一段判断一下连续的0的个数

            st[i]  = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
        }

        //第二部分：预处理2
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突

        for (int j = 0; j < (1 << n); j ++) { //对于第i列的所有状态
            state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。

            for (int k = 0; k < (1 << n); k ++) { //对于第i-1列所有状态
                if ((j & k ) == 0 && st[ j | k]) 
                // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                //解释一下st[j | k] 
                //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，
                //还要考虑自己这一列（i-1列）横插到第i列的
                //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                //那么合在第i-1列，到底有多少个1呢？
                //自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
                //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的

                    state[j].push_back(k);  
                    //二维数组state[j]表示第j行， 
                    //j表示 第i列“真正”可行的状态，
                    //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                    //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }

        }

        //第三部分：dp开始

        memset(f, 0, sizeof f);  
        //全部初始化为0，因为是连续读入，这里是一个清空操作。
        //类似上面的state[j].clear()

        f[0][0] = 1 ;// 这里需要回忆状态表示的定义
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。
        //其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for (int i = 1; i <= m; i ++) { //遍历每一列:第i列合法范围是(0~m-1列)
            for (int j = 0; j < (1<<n); j ++) {  //遍历当前列（第i列）所有状态j
                for (auto k : state[j])    // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i-1][k];    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }

        //最后答案是什么呢？
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数

        cout << f[m][0] << endl;

    }
} 

最短Hamilton路径

题目：最短Hamilton路径

思路：用二进制来表示要走的所以情况的路径,这里用 i 来代替
例如走 0,1,2,4 这三个点,则表示为:10111;
走 0,2,3 这三个点: 1101;

假设: 一共有七个点,用 0,1,2,3,4,5,6 来表示,那么先假设终点就是 5,在这里我们再假设还没有走到 5 这个点,且走到的终点是 4,那么有以下六种情况:
first: 0–>1–>2–>3–>4 距离:21
second: 0–>1–>3–>2–>4 距离:23
third: 0–>2–>1–>3–>4 距离:17
fourth: 0–>2–>3–>1–>4 距离:20
fifth: 0–>3–>1–>2–>4 距离:15
sixth: 0–>3–>2–>1–>4 距离:18

状态：$f[i][j]$ 所有从 0 走到 j,走过的所有点的情况是i的所有路径最短距离

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20, M = 1 << N;
int w[N][N];
int f[M][N];


int main()
{   
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            cin >> w[i][j];
        
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;//0 到 0 距离为 0
    
    for (int i = 0; i < (1 << n); i ++ )// 遍历每一种状态情况
        for (int j = 0; j < n; j ++ )// 遍历每个点
            if(i >> j & 1)// 看 j 号点是否存在
                for (int k = 0; k < n; k ++ ) // 找出以 k 为终点的路径
                    if(i >> k & 1)// 看终点是否存在
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);//算出以 k 为终点的路径(不包括 j 号点) + k 到 j 的唯一路径
    
    cout<< f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

数位dp

计数问题

题目：计数问题

思路：

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int getn(int x){ // 获取数字的位数
    int res = 0;
    while(x) x /= 10, res ++;
    return res;
}

int count(int n, int i){//找出0 ~ n 数字 i 的个数
    int len = getn(n), res = 0;
    for(int j = 1; j <= len; j ++){ //遍历数字每一位数
    int p = pow(10, len - j), l = n / p / 10, di = n / p % 10, r = n % p;
    /* 找出以每一位数字 di 为中点的左部分 l 和 右部分 r 的数字
        例如： abcdefg
        l = abc , di = d , r = efg    
    */
    if(i) res += l * p;//分状况讨论 j 位上 数字 i 的所有情况
    else res +=(l - 1) * p;
    
    if(di == i) res += r + 1;
    if(di > i) res += p;
    }
    return res;
    
}
int main(){
    int a, b;
    while(cin >> a >> b, a || b){
        if(a > b)swap(a, b);
        for(int i = 0; i <= 9; i ++){
            cout << count(b, i) - count(a - 1, i) << ' ';
        }     
        cout << endl;
    }
    return 0;
}

记忆化搜索

滑雪

题目：滑雪

题意：一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

状态：$f[i][j]$ 从位置（i，j）走过的最多区域

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 310;
int n, m, f[N][N], g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


int dp(int x, int y){
    int &v = f[x][y];// 引用别名，v 变化 f[i][j] 变化
    if(v != -1)return v;// 如果走过直接返回 ，减少重复计算步骤
    v = 1;//初始化每个点为 1
    for (int i = 0; i < 4; i ++ ){ //搜索四个方向
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if(xx <= n && xx >= 1 && yy <= m && yy >= 1 && g[xx][yy] < g[x][y])
            v = max(v, dp(xx, yy) + 1);
    }
    return v;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];
            
    int res = 0;
    memset(f, -1, sizeof f);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));//遍历每一个位置
            
    cout << res << endl;
}   

计数类dp

整数划分

题目：整数划分

思路：把 1,2,3, … n 分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）

#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int n;

int main()
{
    cin >> n;
    f[0] = 1;//容量为0时，前 i 个物品全不选也是一种方案
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j ++){
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n] << endl;
    return 0;
}