【DP 动态规划 | 精选推荐】持续更新

前言

本文（DP 动态规划）章节，主要记录一些比较经典，或者说是容易理解的动态规划习题，难度一般都不会很大（$\le Medium$）。

1. 乘积为正数的最长子数组长度

乘积为正数的最长子数组长度

状态定义：

• $f[i][0/1]$：以 $i$ 结尾的乘积为正（$0$）/负（$1$）的最大长度。
• 转移见代码注释那几行，容易理解。

由于转移只用到上一层状态，所以可以用两个变量来替代。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size(); 
        // int f[n + 1][2];
        int res = 0;
        // f[0][0] = f[0][1] = 0;
        int f = 0, g = 0;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            if (x == 0) f = g = 0; //f[i][0] = f[i][1] = 0;
            else if (x > 0) {
                // f[i][0] = f[i - 1][0] + 1;
                // f[i][1] = f[i - 1][1] ? (f[i - 1][1] + 1) : 0;
                f++;
                g = g ? (g + 1) : 0;
            } else if (x < 0) {
                // f[i][0] = f[i - 1][1] ? (f[i - 1][1] + 1) : 0; 
                // f[i][1] = f[i - 1][0] + 1;
                int t = f;
                f = g ? g + 1 : 0;
                g = t + 1;
             }

            res = max(res, f);
        }
        return res;
    }
};

2. 矩阵中和能被 K 整除的路径

矩阵中和能被 K 整除的路径

状态定义：

• $f[i][j][k]：$ 走到$[i,j$]余数为$k$的路径数。
• 转移：用余数进行转移就行了。

class Solution {
public:
    
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid[0].size(); 
        vector<vector<vector<int>>> f(n, vector<vector<int>>(m, vector<int>(52, 0)));
        constexpr static int mod = 1e9 + 7;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int x = 0; x < k; x++) f[i][j][k] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int x = 0; x < k; x++) {
                    int now = grid[i][j];
                    now %= k;
                    int t = (now + x) % k;
                    if (i == 0 && j == 0) {
                        f[i][j][now] = 1;
                        break; 
                    } else if (i == 0) {
                        f[i][j][t] += f[i][j - 1][x];
                        f[i][j][t] %= mod;
                    } else if (j == 0) {
                        f[i][j][t] += f[i - 1][j][x];
                        f[i][j][t] %= mod;
                    } else {
                        f[i][j][t] += f[i - 1][j][x] + f[i][j - 1][x];
                        f[i][j][t] %= mod;
                    }
                }
            }
        }
        return f[n - 1][m - 1][0] % mod;
    }
};

3. 使序列递增的最小交换次数

使序列递增的最小交换次数

状态定义：

• $f[i][0/1]：$ 以 $i$ 为结尾的，且当前第 $i$ 位交换（1）/ 不交换（0）的最小交换次数。

class Solution {
public:
    int minSwap(vector<int>& a, vector<int>& b) {
        int n = a.size(); 
        int f[n][2];
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0, f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i - 1] && b[i] > b[i - 1]) {
                f[i][0] = min(f[i][0], f[i - 1][0]);
                f[i][1] = min(f[i][1], f[i - 1][1] + 1);
            } 
            if (a[i] > b[i - 1] && b[i] > a[i - 1]) {
                f[i][0] = min(f[i][0], f[i - 1][1]);
                f[i][1] = min(f[i][1], f[i - 1][0] + 1);
            }
        }
        return min(f[n - 1][1], f[n - 1][0]);
    }
};

4. Kate and Company Management

Kate and Company Management

题意：

n个数，划分不同组，每组相邻的两数gcd不为1，不相邻的可以不满足该条件。问组的最大划分个数，若个数 $\le 3$输出 $-1$。

思路：

dp + 分解质因数

状态定义：

• $f[i]：$ 以 $i$ 位为结尾最大组成个数。
• $pre[x]：$ 因数为 $x$ 的最大组成个数。

状态转移：

$a[i]$ 的所有因数 $x_1,x_2,..{.}_{,}{x}_n$ ：

• $f[i]=f[x_i]+1$

在转移完 $f[i]$ 后，需要更新当前 $a_i$ 的所有因数在此时能组成的最大个数：

• $pre[x]=f[i]$

int n;
int a[N];
int f[N], pre[N]; 
vi v[N];

// nlogn 打出质因数
void init() {
	for (int i = 1; i <= a[1]; i++) {
		for (int j = 1; j <= a[1] / i; j++) {
			v[i * j].pb(i);
		}
	}
}

void solve() {
	cin >> n;
	rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + 1+ n, [=](int i, int j){ return i > j; }); 
	init(); 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < v[a[i]].sz; j++) {
			int x = v[a[i]][j];
			f[i] = max(f[i], pre[x] + 1); 
		}
		for (int j = 1; j < v[a[i]].sz; j++) {
			int x = v[a[i]][j];
			pre[x] = f[i];
		} 
	}
	int res = 0;
	for (int i = 1; i <= n; i++) res = max(res, f[i]);
	if (res < 3) res = -1;
	cout << res << endl; 
}

5. Good Key, Bad Key

Good Key, Bad Key

题意：

n个箱子，每个箱子打开有收益 $a_i$，选择好钥匙打开需要花费固定值 $m$，坏钥匙打开第 $i$ 个箱子花费0，但是会导致后面 $i,i+1,...n$ 的箱子收益减半。问最大收益。

状态定义：

• $f[i][j]：$ 开了 $i$ 个箱子，使用了 $j$ 把坏钥匙的最大收益。

另解： 贪心

结论是，bad key 后面一定不存在 good key，即 ggggggbbbbb。

x, y
1. good then bad: x + y / 2 - m
2. bad then good: x / 2 + y / 2 - m

int n, m;
int f[N][65], a[N], s[N];

void solve() {
	int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    for(int i = 1; i <= n; i ++) {
        f[i][0] = f[i - 1][0];
        // f[i][0] = s[i] - m * i;
        for(int j = 1; j <= 63; j ++) {
            f[i][j] = max(f[i - 1][j - 1] + (a[i] >> j), f[i - 1][j] - m + (a[i] >> j));
        }
    }
    int ans = -2e18;
    for(int i = 1; i <= 63; i ++) ans = max(ans, f[n][i]);
    cout << ans << endl;
    return ;
}

6. Vladik and Memorable Trip

Vladik and Memorable Trip

题意：

n 个数，挑一些区间，所有值进行异或求最大。但是需要满足条件是，区间中出现的数 $x$，不能在出现在挑选的区间外。

状态定义：

• $f[i]：$ 前 $i$ 个人中挑选区间的最大值。

状态转移：

维护每个值的最左和最右下标，枚举包含以 $i$ 为结尾的区间的情况转移。

$O(n^2)dp$，$st$数组用来去重，一个数只运算一次（相同的数异或不就白给，想读题点上方传送门）。

int n;
int a[N];
int L[N], R[N];
int f[N];
bool st[N];

void solve() {
	cin >> n;
	memset(L, 0x3f, sizeof L);
	rep(i, 1, n) { 
		cin >> a[i];
		L[a[i]] = min(L[a[i]], i);
		R[a[i]] = max(R[a[i]], i);
	}
	for (int i = 1; i <= n; i++) {
		f[i] = f[i - 1];
		memset(st, 0, sizeof st);
		int l = L[a[i]];
		int res = 0;
		for (int j = i; j >= 1; j--) {
			if (!st[a[j]]) {
				if (R[a[j]] > i) break; 
				l = min(l, L[a[j]]);
				res ^= a[j];
				st[a[j]] = 1;
			}
			if (j <= l) f[i] = max(f[i], f[j - 1] + res);
		}
	}
	cout << f[n] << endl;
}