前缀DP

前缀和

给定⼀个数组 a ，求出所有起点到当前位置的和

f[i] = f[i-1] + a

前缀最大值

f[i] = max(f[i-1], a)

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同的⽅法爬到楼顶呢？

状态：f[i]表示从起点到阶梯i有多少种方式

状态转移：f[i] = f[i - 1] + f[i - 2]

拓展：每次向上一步或者向下直接跳到楼底，问k次行动后，到达第x阶台阶的方案数（以行动次数找状态）

最大子数组和

给一个整数数组nums，找出一个最有最大和的连续子数组（子数组最少包含一个元素），返回其最大值

状态：f[i]表示以当前节点i结尾的子数组的最大值

则f[i] = max(f[i] + ai)

以问题做状态、以i开头、以i结尾作为状态定义

过河卒

类似二维dp或者双重前缀dp吧

滚动数组

利用奇偶性，把i % 2这个数组当作当前阶段,1 - i % 2当作上一阶段

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> dp(2, vector<int>(m + 1));
for(int i = 0; i <=n; i ++){
    auto &cur = dp[i % 2], &pre = dp[1 - i % 2];
    auto &cur = dp[i & 1], &pre = dp[~i & 1]
    for(int j = 0; j <= m; j ++){
        if(blocked[i][j]) cur[j] = 0;
        else if(i == 0 && j == 0) cur[j] = 1;
        else if(i == 0) cur[j] = cur[j - 1];
        else if(j == 0) cur[j] = pre[j];
        else cur[j] = pre[j] + cur[j - 1];
    }
}

有奖问答

一共答n题，每答对一次分数加1，答错分数清0，可以随时停止作答，问有多少种方案最终可以拿到k分

状态：f[i][j]表示答了i题，分数为j的方案数

打家劫舍

你是⼀个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有⼀定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被小偷闯⼊，系统会自动报警。给定⼀个代表每个房屋存放金额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼金额。

状态：f[i][-], i表示偷到第几家，-为0、1，表示是否偷了这一家，f[i][j]为当前最大偷窃金额

状态转移：f[i-1][0] -> f[i][0] || f[i][1] f[i-1][1] -> f[i][0]

1
2
3
4
5
6
7
8
int n = nums.size();
auto dp = vector(n, vector(2, 0));
dp[0][1] = nums[0];
for (int i = 1; i < n; i ++) {
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
	dp[i][1] = dp[i - 1][0] + nums[i];
}
return max(dp[n-1][0], dp[n-1][1]);

打家劫舍（二）

上题的衍生，房屋围成一圈

状态：f[i][robber][first],first额外记录第一个节点有没有偷窃，用于判断最后的合法状态

1
2
3
4
5
6
7
8
9
10
if (n == 1) return nums[0];
auto dp = vector(n, vector(2, vector(2, 0)));
dp[0][1][1] = nums[0];
for (int i = 1; i < n; i ++) {
	for (int first = 0; first < 2; first ++) {
		dp[i][0][first] = max(dp[i-1][0][first], dp[i-1][1][first]);
		dp[i][1][first] = dp[i-1][0][first] + nums[i];	
	}
}
return max({dp[n-1][1][0], dp[n-1][0][0], dp[n-1][0][1]});

01DP

最高乘法得分

最大的和

最大的乘积

DAG DP

二维DP

背包DP

划分DP

全排列DP