DP笔记

发表于2025-12-07|更新于2025-12-07

|浏览量:

DP题目的特点

数据较小，至少有一维是可以接受的，比如每一步的决策小于3，总数小于1000等等
每一步的答案可以由之前的答案得到，比如数字三角形

DP题目的大致做法

设DP数组

明确DP数组的含义，保证每次求解的答案都是这个含义，不然就可能出错
(这也是我之前的一大误区)

分类讨论

明确有几种决策方案，明确这一步的答案是怎么推断出来的(非常重要!!!)

接下来编写代码就行了

举例：迎新赛M题

题目传送门：

ZJUTOJ | 2024ZJUT迎新赛-决赛-M. 三色小屋

题目理解：

首先发现每一步的方案数可以接受，并且这一步的答案只由上一步转移而来，所以可以使用DP
每个位置只能填R/G/B三种颜色，而且之和上一步和相邻的颜色有关，几种方案互不影响，符合动态规划的特点

分类讨论：
分为两大类，因为开头要初始化，所以单独讨论

$dp[i][j] = \begin{cases} i==1\begin{cases} c[i]==\ '0' & \text{可以用的颜色为1} \\ c[i]\ !=\ \ '0' & \text{这个颜色为1} \end{cases}\\ \\ i\ !=1\begin{cases} c[i]==\ '0' & \text{可以填入的颜色为前两个的和} \\ c[i] \ !=\ \ '0' & \text{这个颜色为前两个的和} \end{cases} \end{cases}$

DP概率题

求期望的几个重要公式

$\begin{aligned} E(aX+b)=aE(x)+b \\ \\ E(X+Y)=E(X)+E(Y)\\ \\ E(XY)=E(X)E(Y) \end{aligned}$

上面两个说明了期望的线性关系，下面两个说明了期望的独立性

文章作者: ZestfulYK

文章链接: https://zestfulyk.github.io/ZestfulYK-blog/2025/12/07/DP%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZestfulYK的Blog！

相关推荐

算法挑战赛题解（11.2）

算法挑战赛题解（11.2）简单版本：题目大意：给定n个区间，判断这些区间能划分出几种不同的区域性质不同的数字题目分析：实际上是在讨论每个点被哪几个区包含，在样例中，数据是这样的，我们来分析一下这两个样例 123456789101112131415161718192021Sample Input 1 11 6Sample Output 12Sample Input 240 124 136 1312 13Sample Output 26 样例分析：12345678样例1: 0 1 1 1 1 1 1 0 0 … … 所以是两种区间样例2: 1 2 3 4 5 6 7 8 9 10 11 12 13 … … 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 ...

简单题对于简单题目，最好还是仔细一点，或者使用最暴力的解法，而不是投机取巧，或者构造高级方法，通常样例数据都是片面的，常常会有坑。 sleeping through classes 比如这一题，数据没有包含i+k中间有1的情况，直接i+=k导致错误。中等题目中等题目就需要强观察力和trick技巧了 Niko’s Tactical Cards 这一道题目是动态规划的变种，虽然要求每一步最优，但是可能发生最小值突然转变成最大值的情况，因此，计算最小值也是必要的。只要计算这两个值就行了。 Kanade’s Perfect Multiples 这题希望我们构造一个满足要求的B，这个就有点类似于筛法求素数了，实际上两者的代码几乎是一样的，但是在做的时候要注意区分原始数据和v数组，一个一个遍历就行了，找不到就可以直接退出，因为不然当前确定的最小值就无法被覆盖了。 Merging the Sets 你想选择其中的一些集合（可能一个都不选，也可能全部都选），使得 1 和 m 之间的每个整数都包含在个所选集合中的至少一个中。思维误区，不用一边读入一边判断，因为数据保证$l\leq 2*1...

模运算性质总结

模运算（Mod）性质总结定义对于任意实数 $( x, y )$，有： x \mod y = x - y \left\lfloor \frac{x}{y} \right\rfloor, \quad y \neq 0模运算（在一些场合使用符号 % 表示）是一个二元运算。$( x \mod y )$ 的值范围如下：当 $( y > 0 )$ 时：$( 0 \leq x \mod y < y )$ 当 $( y < 0 )$ 时：$( 0 \geq x \mod y > y )$ 当 $( y = 0 )$ 时：为避免除以零，定义 $( x \mod 0 = x )$ 基本运算规则模运算与基本四则运算类似（除法除外）：加法规则：$((a + b) \mod p = (a \mod p + b \mod p) \mod p)$ 减法规则：$((a - b) \mod p = (a \mod p - b \mod p) \mod p)$ 乘法规则：$((a \times b) \mod p = (a \mod p \times b \mod p) \mod ...

全排列函数的应用

全排列函数什么是全排列？简单来说就是排列组合的所有情况，并按照字典顺序输出例如：123全排列的结果为 123456123132213231312321 而实际上全排列需要在代码中用复杂的深度搜索来写这实在是太复杂了！！！于是我就发现了全排列函数这个东西^__^现在我们就来学习一下这个高级函数————next_permutation 全排列函数123456789101112#include <iostream> #include <algorithm> using namespace std; int main() { int num[3]={1,2,3}; do { cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl; }while(next_permutation(num,num+3)); ...

前缀和笔记

前缀和定义前缀和（Prefix Sum）是一种重要的预处理技术，能在O(1)时间内查询区间和，在算法竞赛和面试中应用广泛。以下是前缀和的主要应用场景和变种： 1. 基本前缀和计算$\Sigma_{i=1}^n a_i$的值，用来求区间和例如：1234567// 一维前缀和vector<int> pre(n+1, 0);for (int i = 1; i <= n; i++) { pre[i] = pre[i-1] + a[i];}// 查询区间[l, r]的和int sum = pre[r] - pre[l-1]; 2. 二维前缀和用于计算矩阵的和$\Sigma{i=1}^n\Sigma{j=1}^na_{ij}$ 12345678vector<vector<int>> pre(m+1, vector<int>(n+1, 0));for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { ...

华中农业达大学迎新赛题解与反思

M-终极考验这题的大致思路是对的，但是最后处理差分时，直接选择了min(i+x,n)，这个就不对了，因为我们要的不是二选1，而是只有在满足要求时才处理。所以把min改成if判断就行了，下次需要注意这个逻辑问题。 H-对决这个题目是纯暴力的搜索题，那么只要一个一个判断就好了，但是此处注意循环范围是$\leq n-4$而不是$<n-4$.最好自己先之上推导一下再提交 B-爱的魔法这一题一开始的错误原因是没有注意到交换最接近的会导致得到的不是最大的数字，例如1999，交换以后是9199是不对的，所以要倒遍历。建议自己先多造几组数据再提交，包括一些边界情况等等。随机数也不错（较小范围能手推的）