5）动态规划

文章目录

• DP 问题能用记忆化搜索写的话推荐用记忆化搜索，代码复杂度低，比较容易想！！！
• 背包问题
• • 01背包问题
  • 完全背包问题
  • 多重背包问题
  • 多重背包问题 II
  • 分组背包问题
• 线性DP
• • 数字三角形
  • 最长上升子序列
  • 最长上升子序列 II
  • 最长公共子序列
  • 最短编辑距离
  • 编辑距离
• 区间DP
• • 石子合并
• 计数类DP
• • 整数划分
• 数位统计DP
• • 计数问题
• 状态压缩DP
• • 蒙德里安的梦想
  • 最短Hamilton路径
• 树形DP
• • 没有上司的舞会
• 记忆化搜索
• • 滑雪

---

DP 问题能用记忆化搜索写的话推荐用记忆化搜索，代码复杂度低，比较容易想！！！ 背包问题

用滚动数组优化时，
如果需要的是上一层的状态，则需要从大到小枚举本层状态
如果需要的是本层的状态，则从小到大枚举本层状态

01背包问题

/*
f[i, j]: (1~i)物品选, 容量不超过j的max价值
划分为两个集合：
1) 不包含i的集合
  (1~i中选,不包含i) f[i-1,j]
2) 包含i的集合
  曲线救国：这个集合中所有方案都包含i,所以可以先算取掉i后,价值最大的,然后加上i的价值
  f[i-1, j-v[i]] + wi

f[i, j] = max(f[i-1, j], f[i-1, j-v[i]]+wi)
*/
#include

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main(){
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    // 优化版
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

完全背包问题

/*
f[i, j] = f[i-1, j-v[i]*k]+k*w[i]
优化： f[i,j] = Max(f[i-1,j], f[i-1, j-v]+w. f[i-1,j-2v]+2w, f[i-1,j-3v]+3w,,...)
    f[i, j-v] = Max(          f[i-1, j-v],   f[i-1,j-2v]+w,  f[i-1,j-2v]+2w,....)
所以：f[i,j] = max(f[i,j-v] + w, f[i-1][j])

可以继续优化成滚动数组
*/
#include

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main(){
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++){
        for(int j = v[i]; j <= m; j++){
            
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

多重背包问题

/*

f[i, j] = max(f[i - 1, j - k * v[i] + w[i] * k)  k = 0,1,2,...,s[i]

*/
#include

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main(){
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
                
                f[i][j] = max(f[i][j], f[i-1][j-v[i]*k] + w[i]*k);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

多重背包问题 II

#include

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main(){
    
    cin >> n >> m;
    
    int cnt = 0;
    
    for(int i = 1; i <= n; i++){
        
        int a, b, s;
        cin >> a >> b >> s;
        
        // 拆分s为 1, 2, 4, 8, 16,...,2^k, c
        int k = 1;
        while(k <= s){
            
            cnt++;
            // k件物品对应的体积和价值
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        // 计算c
        if(s > 0){
            
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;
    
    // 转换成01背包
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

分组背包问题

#include

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(){
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        
        cin >> s[i];
        
        for(int j = 0; j < s[i]; j++){
            
            cin >> v[i][j] >> w[i][j];    
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 0; j--){
            for(int k = 0; k < s[i]; k++){
                
                if(v[i][k] <= j){
                    
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

线性DP 数字三角形

左上|右上

#include

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main(){
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    
    // 初始化边界为 -INF
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            f[i][j] = -INF;
        
    f[1][1] = a[1][1];
    
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    
    int res = -INF;
    for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    
    return 0;
}

最长上升子序列

#include

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main(){
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++){
        
        f[i] = 1; // 只有a[i] 一个数
        for(int j = 1; j < i; j++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);       
    }
    
    int res = 0;
    
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    
    printf("%d\n", res);
    
    return 0;
}

最长上升子序列 II

可以从 O(n^2) 优化到 O(nlogn)
q[i] 的意思是 i 长度的子序列中，最小的子序列
保证当前 q[i] 是 i 长度中最小的数

#include

using namespace std;

const int N = 100010;

int n;
int q[N], a[N];

int main(){
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    int len = 0;
    for(int i = 1; i <= n; i++){
        int l = 1, r = len + 1;
        while(l < r){
            
            int mid = l + r >> 1;
            if(a[i] <= q[mid]) r = mid;
            else l = mid + 1;
        }
        q[r] = a[i];
        len = max(len, r);
    }
    
    printf("%d\n", len);
    
    return 0;
}

最长公共子序列

#include

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main(){
    
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

最短编辑距离

#include

using namespace std;

const int N = 1010;

int n, m;
char s1[N], s2[N];
int f[N][N];

int main(){
    
    scanf("%d%s%d%s", &n, s1 + 1, &m, s2 + 1);
    
    for(int i = 1; i <= n; i++) f[i][0] = i;
    for(int i = 1; i <= m; i++) f[0][i] = i;
    
    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);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (s1[i] != s2[j]));
        }
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

编辑距离

#include
#include
#include

using namespace std;

const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

// dp求编辑距离
int edit_distance(char a[], char b[]){
    
    int la = strlen(a + 1), lb = strlen(b + 1);
    
    for(int i = 0; i <= lb; i++) f[0][i] = i;
    for(int i = 0; i <= la; i++) f[i][0] = i;
    
    for(int i = 1; i <= la; i++){
        for(int j = 1; j <= lb; j++){
            
            f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
            f[i][j] = min(f[i][j], f[i-1][j-1] + (a[i] != b[j]));
        }
    }
    
    return f[la][lb];
}


int main(){
    
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%s", str[i] + 1);
    
    while(m--){
        
        char s[N];
        int limit;
        
        scanf("%s%d", s + 1, &limit);
        
        int res = 0;
        
        for(int i = 0; i < n; i++)
            if(edit_distance(str[i], s) <= limit) res++;
        
        printf("%d\n", res);
    }
    
    
    return 0;
}

区间DP 石子合并

#include

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main(){
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
    
    for(int i = 1; i <= n; i++) s[i] += s[i - 1];
    
    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++){
                
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    
    printf("%d\n", f[1][n]);
    
    return 0;
}

计数类DP 整数划分

解法一

完全背包解法
状态表示：
f[i][j] 表示只从1~i中选，且总和等于j的方案数

状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - i];

/*
f[i,j] = f[i-1,j]+f[i-1,j-i]+f[i-1][j-2*i]+...+f[i-1][j-k*i];
f[i,j-i] =        f[i-1,j-i]+f[i-1][j-2*i]+...+f[i-1][j-k*i];
f[i,j] = f[i-1,j]+f[i,j-i];
*/
#include

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main(){
    
    scanf("%d", &n);
    
    f[0] = 1;
    
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % mod;
    
    printf("%d\n", f[n]);
    
    return 0;
}

解法二

其他算法
状态表示：
f[i][j] 表示总和为 i，总个数为 j 的方案数

状态转移方程：
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

#include

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main(){
    
    cin >> n;
    
    f[1][1] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
            
    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    
    cout << res << endl;
    
    return 0;
}

数位统计DP 计数问题

/*
在1~n中统计x出现的次数 x > 0; x = 0
n = abcdefg, 假如统计的是x在第i = 4位出现的次数
x > 0
1) 前面三位取从 000 ~ abc - 1时, 此时已经小于abc了,所以后面的3位可以任取, 000 ~ 999 (res += abc * 1000)
2) 前面三位取abc时
  2.1) d < x  res += 0
  2.2) d = x  后三位只能取(000~efg), res += (efg+1)
  2.3) d > x  此时后三位任取 (000~999) res += 1000
注意x > 0, i = 1时,前面没有数, 无 1) 这种情况

x = 0
1) 前面三位取从 001 ~ abc - 1时, 此时已经小于abc了,所以后面的3位可以任取, 000 ~ 999 (res += (abc-1) * 1000)
2) 前面三位取abc时
  2.1) d < x  res += 0
  2.2) d = x  后三位只能取(000~efg), res += (efg+1)
  2.3) d > x  此时后三位任取 (000~999) res += 1000

x = 0时, i不存在i=1的情况
*/

#include
#include

using namespace std;

const int N = 10;

// 计算num的第l ~ r位和是多少
int get(vector<int> num, int l, int r){
    
    int res = 0;
    for(int i = l; i >= r; i--) res = res * 10 + num[i];
    return res;
}


// 10^x
int power10(int x){
    
    int res = 1;
    while(x--) res *= 10;
    return res;
}


int count(int n, int x){
    
    if(!n) return 0;
    
    vector<int> num;
    // 将每一位拆开(低位在前)
    while(n){
        
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size();
    
    int res = 0;
    // 从高位到低位, 统计x在当前位出现的次数
    for(int i = n - 1 - !x; i >= 0; i--){
        
        // 000 ~ abc - 1
        if(i < n - 1){
            
            res += get(num, n - 1, i + 1) * power10(i);
            // x == 0时 前面需要从001开始，而不是000
            if(!x) res -= power10(i);
        }
        
        // abc
        // d == x
        if(num[i] == x) res += get(num, i - 1, 0) + 1;
        else if(num[i] > x) res += power10(i);   // d > x
    }
    
    return res;
}

int main(){
    
    int a, b;
    
    while(cin >> a >> b, a){
        
        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;
}

状态压缩DP 蒙德里安的梦想

/*
核心: 先放横着的, 再放竖着的。


总方案数: 等于只放横着的小方块的合法方案数
如何判断,当前方案是否合法?  
所有剩余位置,能否填充满竖着的小方块。


可以按列看,每一列内部所有连续的空着的小方块,需要是偶数个
*/

#include
#include
#include

using namespace std;

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

int n, m;
// dp
long long f[N][M];
// 预处理出来哪些 k -> j 是合法的, 即预处理出能转移到j状态的对应的合法的k有哪些
vector<int> state[M];
// 判断某个状态是否合法, 即对于当前列,所有空着的连续的方格是否偶数(能否被竖着的方格塞满)
bool st[M];

int main(){
    
    while(cin >> n >> m, n || m){
        
        // 预处理st数组
        for(int i = 0; i < 1 << n; i++){
            
            int cnt = 0;  // 连续的0的个数
            bool is_valid = true;  // 判断是否合法
            for(int j = 0; j < n; j++){
                
                if(i >> j & 1){
                    
                    // 0为奇数个,则已经不合法
                    if(cnt & 1){
                        
                        is_valid = false;
                        break;
                    }
                    
                    cnt = 0;
                }else{
                    
                    cnt++;
                }
            }
            // 判断下面最后一段0个数是否合法
            if(cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
        
        // 预处理state合法转移数组
        for(int j = 0; j < 1 << n; j++){
            // k -> j
            state[j].clear();
            for(int k = 0; k < 1 << n; k++){
                
                // 第i-1列空着的位置是否合法 (k | j)的结果就是空着的
                // 因为k是从i-2伸到i-1列, j是从i-1列伸到第i列
                if((k & j) == 0 && st[k | j]){
                    
                    state[j].push_back(k);
                }
            }
        }
        
        memset(f, 0, sizeof(f));
        
        // 空棋盘为一种状态
        f[0][0] = 1;
        
        for(int i = 1; i <= m; i++){
            
            for(int j = 0; j < 1 << n; j++){
                
                for(auto k : state[j]){
                    
                    f[i][j] += f[i - 1][k];
                }
            }
        }
        
        cout << f[m][0] << endl;
    }
    
    return 0;
}

最短Hamilton路径

#include
#include

using namespace std;

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

int n;
int w[N][N];  // 邻接矩阵
int f[M][N];  // dp

int main(){
    
    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));
    // 从0走到0这个点, 只经过了0,所以i的第一个二进制位是 1
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i++){
        for(int j = 0; j < n; j++){
            // 从0 ~ j, i里面一定要包含j
            if(i >> j & 1){
                // 枚举倒数第二个点
                for(int k = 0; k < n; k++){
                    // 从第k个点转移过来, 则i除去j这个点之后必须包含k这个点
                    if(i - (1 << j) >> k & 1){
                        
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
                }
            }
        }
    }
    
    // i从1 ~ n位全为1; j = n - 1
    cout << f[(1 << n) - 1][n - 1] << endl;
    
    return 0;
}

树形DP 没有上司的舞会

#include
#include

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;  // 邻接表存储边
int happy[N];  // 每个点的H值
int f[N][2];  // dp
bool has_fa[N];  // 是否有父节点

void add(int a, int b){
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
    
    f[u][1] = happy[u];
    
    for(int i = h[u]; i != -1; i = ne[i]){
        
        int j = e[i];
        dfs(j);
        
        // 状态转移
        f[u][1] += f[j][0];  // f[u, 1] = Hu + sum(f(si, 0))
        f[u][0] += max(f[j][0], f[j][1]);  // f[u, 0] = sum(max(f(si, 0), f(si, 1)))
    }
}

int main(){
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++) scanf("%d", &happy[i]);
    
    memset(h, -1, sizeof(h));
    for(int i = 0; i < n - 1; i++){
        
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = true;
    }
    
    int root = 1;
    while(has_fa[root]) root ++;
    
    dfs(root);
    
    printf("%d\n", max(f[root][0], f[root][1]));
    
    return 0;
}

记忆化搜索 滑雪

#include
#include

using namespace std;

const int N = 310;

int n, m;
int g[N][N];
int f[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];
    if(v != -1) return v;
    
    v = 1;
    for(int i = 0; i < 4; i++){
        
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]){
            
            v = max(v, dp(a, b) + 1);
        }
    }
    
    return v;
}

int main(){
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            
            scanf("%d", &g[i][j]);
        }
    }
    
    memset(f, -1, sizeof(f));
    
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            //  枚举每一个起点
            res = max(res, dp(i, j));
        }
    }
    
    printf("%d\n", res);
    
    return 0;
}