Acwing《算法基础课》第5章 动态规划

    科技2024-04-03  17

    Acwing《算法基础课》第5章 动态规划

    文章目录

    Acwing《算法基础课》第5章 动态规划背包问题01背包问题完全背包问题多重背包问题分组背包问题 线性DP数字三角形最长上升子序列最长公共子序列最短编辑距离 区间DP计数类DP完全背包解法其它算法 数位统计DP状态压缩DP蒙德里安的梦想最短Hamilton路径 树形DP记忆化搜索


    背包问题

    01背包问题

    n n n个物品,每个物品的体积是 v i v_i vi,价值是 w i w_i wi,背包的容量是 m m m

    若每个物品最多只能装一个,且不能超过背包容量,则背包的最大价值是多少?

    模板

    int n; // 物品总数 int m; // 背包容量 int v[N]; // 重量 int w[N]; // 价值 // ---------------二维形式--------------- int f[N][M]; // f[i][j]表示在考虑前i个物品后,背包容量为j条件下的最大价值 for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(j < v[i]) f[i][j] = f[i-1][j]; // 当前重量装不进,价值等于前i-1个物品 else f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]); // 能装,需判断 cout << f[n][m]; // ---------------一维形式--------------- int f[M]; // f[j]表示背包容量为j条件下的最大价值 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]; // 注意是m不是n

    说明

    注意f[i][j]的含义:在考虑前i个物品后,背包容量为j条件下的最大价值。而不是表示选了i个物品的最大价值,实际上选择的物品数<=i。f[j]表示背包容量为j条件下的最大价值二维压缩成一维,实际上是寻找避开写后读错误的方法 f[i][j]始终只用上一行的数据f[i-1][...]更新(迭代更新的基础,如果还需用上上行数据则不可压缩)f[i][j]始终用靠左边的数据f[i-1][<=j]更新(决定了只能倒序更新) 显然 i = 0 i=0 i=0时, f ( i , j ) = 0 f(i, j)=0 f(i,j)=0,而初始化时自动赋予 0 0 0,故不必但单独处理第0行

    完全背包问题

    每个物品可以取任意个

    假设背包容量为 j j j时,最多可装入 k k k个物品 i i i,则有 f ( i , j ) = max ⁡ { f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i , f ( i − 1 , j − 2 v i ) + 2 w i , ⋯   , f ( i − 1 , j − k v i ) + k w i } f\left( i,j \right) =\max \left\{ f\left( i-1,j \right) , f\left( i-1,j-v_i \right) +w_i, f\left( i-1,j-2v_i \right) +2w_i,\cdots ,f\left( i-1,j-kv_i \right) +kw_i \right\} f(i,j)=max{f(i1,j),f(i1,jvi)+wi,f(i1,j2vi)+2wi,,f(i1,jkvi)+kwi} 考虑 f ( i , j − v i ) = max ⁡ { f ( i − 1 , j − v i ) , f ( i − 1 , j − 2 v i ) + w i , f ( i − 1 , j − 3 v i ) + 2 w i , ⋯   , f ( i − 1 , j − k v i ) + ( k − 1 ) w i } f\left( i,j-v_i \right) =\max \left\{ f\left( i-1,j-v_i \right) , f\left( i-1,j-2v_i \right) +w_i, f\left( i-1,j-3v_i \right) +2w_i,\cdots ,f\left( i-1,j-kv_i \right) +\left( k-1 \right) w_i \right\} f(i,jvi)=max{f(i1,jvi),f(i1,j2vi)+wi,f(i1,j3vi)+2wi,,f(i1,jkvi)+(k1)wi} 上式变形得 f ( i , j − v i ) + w i = max ⁡ { f ( i − 1 , j − v i ) + w , f ( i − 1 , j − 2 v i ) + 2 w i , f ( i − 1 , j − 3 v i ) + 3 w i , ⋯   , f ( i − 1 , j − k v i ) + k w i } f\left( i,j-v_i \right) +w_i=\max \left\{ f\left( i-1,j-v_i \right) +w, f\left( i-1,j-2v_i \right) +2w_i, f\left( i-1,j-3v_i \right) +3w_i,\cdots ,f\left( i-1,j-kv_i \right) +kw_i \right\} f(i,jvi)+wi=max{f(i1,jvi)+w,f(i1,j2vi)+2wi,f(i1,j3vi)+3wi,,f(i1,jkvi)+kwi} 综上可得 f ( i , j ) = max ⁡ { f ( i − 1 , j ) , f ( i , j − v i ) + w i } f\left( i,j \right) =\max \left\{ f\left( i-1,j \right) ,f\left( i,j-v_i \right) +w_i \right\} f(i,j)=max{f(i1,j),f(i,jvi)+wi} 这样就得优化后的迭代公式,和01背包问题非常相似,但后者用的是 f ( i − 1 , j − v i ) + w i f\left( i-1,j-v_i \right) +w_i f(i1,jvi)+wi

    模板

    int n; // 物品总数 int m; // 背包容量 int v[N]; // 重量 int w[N]; // 价值 // ---------------二维形式--------------- // 未优化 int f[N][M]; // f[i][j]表示在考虑前i个物品后,背包容量为j条件下的最大价值 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 0; k * v[i] <= j; k++) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); // 已优化 int f[N][M]; // f[i][j]表示在考虑前i个物品后,背包容量为j条件下的最大价值 for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(j < v[i]) f[i][j] = f[i-1][j]; // 当前重量装不进,价值等于前i-1个物品 else f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i]); // 能装,需判断 cout << f[n][m]; // ---------------一维形式--------------- int f[M]; // f[j]表示背包容量为j条件下的最大价值 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]; // 注意是m不是n

    说明

    形式上和01背包差不多,在二维数组表示下,主要差别在 在选择第i物品时,用的是f[i][j-v]+w,而不是f[i-1][j-v]+w上述条件决定了在每次迭代时,必须正向遍历,而不是反向遍历 在一维数组表示下,主要差别只表现为迭代的顺序(正向或反向)在一维数组表示下,01背包只能反向是因为它主要用到上一行的数据来更新当前行数据,如果正向遍历,则会修改上一行的数据,出现写后读错误;完全背包只能正向是因为它需要用到当前行的数据更新,如果反向遍历,使用的是上一行的数据,则不符合公式

    多重背包问题

    i i i个物品至多拿 s i s_i si f ( i , j ) = max ⁡ { f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i , f ( i − 1 , j − 2 v i ) + 2 w i , ⋯   , f ( i − 1 , j − s i v i ) + s i w i } f\left( i,j \right) =\max \left\{ f\left( i-1,j \right) , f\left( i-1,j-v_i \right) +w_i, f\left( i-1,j-2v_i \right) +2w_i,\cdots ,f\left( i-1,j-s_iv_i \right) +s_iw_i \right\} f(i,j)=max{f(i1,j),f(i1,jvi)+wi,f(i1,j2vi)+2wi,,f(i1,jsivi)+siwi} f ( i , j − v i ) = max ⁡ { f ( i − 1 , j − v i ) , f ( i − 1 , j − 2 v i ) + w i , f ( i − 1 , j − 3 v i ) + 2 w i , ⋯   , f ( i − 1 , j − s i v i ) + ( s i − 1 ) w i , f ( i − 1 , j − ( s i + 1 ) v i ) + s i w i } f\left( i,j-v_i \right) =\max \left\{ f\left( i-1,j-v_i \right) , f\left( i-1,j-2v_i \right) +w_i, f\left( i-1,j-3v_i \right) +2w_i,\cdots ,f\left( i-1,j-s_iv_i \right) +\left( s_i-1 \right) w_i ,f\left( i-1,j-(s_i+1)v_i \right) +s_i w_i\right\} f(i,jvi)=max{f(i1,jvi),f(i1,j2vi)+wi,f(i1,j3vi)+2wi,,f(i1,jsivi)+(si1)wi,f(i1,j(si+1)vi)+siwi} 变形后得 f ( i , j − v i ) + w i = max ⁡ { f ( i − 1 , j − v i ) + w i , f ( i − 1 , j − 2 v i ) + 2 w i , f ( i − 1 , j − 3 v i ) + 3 w i , ⋯   , f ( i − 1 , j − s i v i ) + s i w i , f ( i − 1 , j − ( s i + 1 ) v i ) + ( s i + 1 ) w i } f\left( i,j-v_i \right) + w_i =\max \left\{ f\left( i-1,j-v_i \right) + w_i, f\left( i-1,j-2v_i \right) +2 w_i, f\left( i-1,j-3v_i \right) +3w_i,\cdots ,f\left( i-1,j-s_iv_i \right) +s_i w_i ,f\left( i-1,j-(s_i+1)v_i \right) +(s_i+1) w_i\right\} f(i,jvi)+wi=max{f(i1,jvi)+wi,f(i1,j2vi)+2wi,f(i1,j3vi)+3wi,,f(i1,jsivi)+siwi,f(i1,j(si+1)vi)+(si+1)wi} 多了一项 f ( i − 1 , j − ( s i + 1 ) v i ) + ( s i + 1 ) w i f\left( i-1,j-(s_i+1)v_i \right) +(s_i+1) w_i f(i1,j(si+1)vi)+(si+1)wi,因此无法按照完全背包的方式优化

    二进制优化

    已知 1 , 2 , 4 , ⋯   , 2 k 1,2,4,\cdots,2^k 1,2,4,,2k可以由系数 0 0 0 1 1 1线性组合出 0 0 0- 2 k + 1 − 1 2^{k+1}-1 2k+11。考虑更一般的情况,若想线性组合出 0 0 0- S S S S < 2 k + 2 S<2^{k+2} S<2k+2,则猜测可由 1 , 2 , 4 , ⋯   , 2 k , C 1,2,4,\cdots,2^k, C 1,2,4,,2k,C组合出,其中 C < 2 k + 1 C<2^{k+1} C<2k+1,显然,在 C C C一定存在的情况下,可得到的数的范围为 C C C- S S S。由于 C < 2 k + 1 C<2^{k+1} C<2k+1,则 C ≤ 2 k + 1 − 1 C\le2^{k+1}-1 C2k+11,故 [ 0 , 2 k + 1 − 1 ] ∪ [ C , S ] ⊇ [ 0 , 2 k + 1 − 1 ] ∪ [ 2 k + 1 − 1 , S ] = [ 0 , S ] \left[ 0,2^{k+1}-1 \right] \cup \left[ C,S \right] \supseteq \left[ 0,2^{k+1}-1 \right] \cup \left[ 2^{k+1}-1,S \right] =\left[ 0,S \right] [0,2k+11][C,S][0,2k+11][2k+11,S]=[0,S],即可用 1 , 2 , 4 , ⋯   , 2 k , C 1,2,4,\cdots,2^k, C 1,2,4,,2k,C表示任何 < 2 k + 2 <2^{k+2} <2k+2的数

    因此对于有s[i]件的某个物品 i i i,可以打包成$\lceil \log s\left[ i \right] \rceil $个物品,每包有 1 , 2 , 4 , ⋯   , 2 k , C 1,2,4,\cdots,2^k, C 1,2,4,,2k,C件物品 i i i,其中$k=\lceil \log s\left[ i \right] \rceil $-1

    int n; // 物品总数 int m; // 背包容量 int v[N]; // 重量 int w[N]; // 价值 // -----------------未优化(完全背包模板)---------------------- int f[N][M]; // f[i][j]表示在考虑前i个物品后,背包容量为j条件下的最大价值 for (int i = 1; i <= n; i++) for (int j = 1; 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 - k * v[i]] + k * w[i]); // -----------------------二进制优化--------------------------- // 读入物品个数时顺便打包 int k = 1; // 当前包裹大小 while (k <= s) { cnt ++ ; // 实际物品种数 v[cnt] = a * k; w[cnt] = b * k; s -= k; k *= 2; // 倍增包裹大小 } if (s > 0) { // 不足的单独放一个,即C 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;

    说明

    用二进制优化后,注意物品种数变成 N × log ⁡ M N\times \log M N×logM,问题转换成01背包问题时间复杂度为 O ( n m log ⁡ s ) O(nm\log s) O(nmlogs)

    分组背包问题

    每组物品中至多拿1个

    实际上是带有约束的01背包问题,状态计算为 f ( i , j ) = max ⁡ { f ( i − 1 , j ) , f ( i − 1 , j − v ( i , k ) ) + w ( i , k ) } f(i, j)=\max \{f(i-1,j),f(i-1,j-v(i,k)) +w(i,k) \} f(i,j)=max{f(i1,j),f(i1,jv(i,k))+w(i,k)}

    模板

    int n; // 物品总数 int m; // 背包容量 int v[N][S]; // 重量 int w[N][S]; // 价值 int s[N]; // 各组物品种数 // 读入数据 for (int i = 1; i <= n; i ++ ) { cin >> s[i]; for (int j = 1; j <= s[i]; j ++ ) cin >> v[i][j] >> w[i][j]; } // 处理数据 for (int i = 1; i <= n; i ++ ) for (int j = m; j >= 1; j -- ) for (int k = 1; 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;

    线性DP

    数字三角形

    核心代码

    // 自顶向下(未压缩`f`) const int INF = 1e9; 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 j = 1; j <= n; j ++ ) res = max(res, f[n][j]);

    说明

    实际上可压缩f,此时只能反向遍历行还可自底向上实现,若压缩,只能正向遍历行可以用0x80初始化f,使得元素都小于-2e9时间复杂度 = O ( 状 态 × 转 移 ) = O ( 1 × n 2 ) = O ( n 2 ) =O(状态\times 转移)=O(1\times n^2)=O(n^2) =O(×)=O(1×n2)=O(n2)

    最长上升子序列

    核心代码

    // 朴素法 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]); // 二分优化 vector<int>stk;//模拟堆栈 stk.push_back(arr[0]); for (int i = 1; i < n; ++i) { if (arr[i] > stk.back()) stk.push_back(arr[i]); // 如果该元素大于栈顶元素,将该元素入栈 else *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i]; // 替换掉第一个大于或者等于这个数字的那个数 } cout << stk.size() << endl; // yxc二分优化 int len = 0; // 最长上升子序列长度(数组q的长度) for (int i = 0; i < n; i ++ ) { // 在数组q中二分查找第1个>= a[i]的数(结果) int l = 0, r = len; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] < a[i]) l = mid; else r = mid - 1; } len = max(len, l + 1); // q[l] < a[i] < q[l + 1] q[l + 1] = a[i]; } printf("%d\n", len);

    说明

    朴素法时间复杂度 = O ( 状 态 × 转 移 ) = O ( n × n ) = O ( n 2 ) =O(状态\times 转移)=O(n\times n)=O(n^2) =O(×)=O(n×n)=O(n2)改进(贪心+二分) 令数组q保存长度为i的上升子序列末尾元素的最小值,例如125和123优先保存123的3,因为它更能接上的后缀种类更多q[]是单调递增的,否则存在q[i-1]>q[i],说明长度为i的上升子序列的最小末尾元素比长度为i-1的还小,这与q[i-1]的定义不符为了使上升子序列最长,应在q[]中找到<a[i]的最大q[j],使得q[j]<a[i]<q[j+1],此时子序列的长度为j+1,且q[j+1]=a[i]。这步用整数二分实现改进后,时间复杂度变为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

    最长公共子序列

    核心代码

    char a[N], b[N]; int f[N][N]; 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]);

    说明

    难点 f ( i − 1 , j ) f(i-1,j) f(i1,j)并不是 01 01 01的等价形式,但 01 ⊆ f ( i − 1 , j ) ⊆ f ( i , j ) 01\subseteq f\left( i-1,j \right) \subseteq f\left( i,j \right) 01f(i1,j)f(i,j),因此 max ⁡ f ( i − 1 , j ) \max f(i-1,j) maxf(i1,j)包含了 max ⁡ ( 01 ) \max(01) max(01),且剩余的部分也是属于 f ( i , j ) f(i,j) f(i,j)的,故可用 f ( i − 1 , j ) f(i-1,j) f(i1,j)代替 01 01 01。同理 f ( i , j − 1 ) f(i,j-1) f(i,j1)可代替 10 10 10 C ⊆ A ∩ B C\subseteq A\cap B CAB,则 max ⁡ ( A , B , C ) = max ⁡ ( A , B ) \max \left( A,B,C \right) =\max \left( A,B \right) max(A,B,C)=max(A,B)。由于 f ( i − 1 , j − 1 ) ⊆ f ( i − 1 , j ) ∪ f ( i , j − 1 ) f\left( i-1,j-1 \right) \subseteq f\left( i-1,j \right) \cup f\left( i,j-1 \right) f(i1,j1)f(i1,j)f(i,j1),故无需考虑 00 00 00的情形,而只需考虑 01 01 01 10 10 10 11 11 11的情况 时间复杂度 = O ( 状 态 × 转 移 ) = O ( n 2 × 1 ) = O ( n 2 ) =O(状态\times 转移)=O(n^2\times 1)=O(n^2) =O(×)=O(n2×1)=O(n2)

    最短编辑距离

    给定两个字符串A和B,只允许对A进行字符插入,字符删除和字符替换,求把A变成B的最少操作次数

    核心代码

    // 初始化边界 for (int i = 0; i <= m; i ++ ) f[0][i] = i; // 把B变成空串需要删除字符的次数 for (int i = 0; i <= n; i ++ ) f[i][0] = i; // 把空串B扩充成A需要插入字符的次数 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 (a[i] == b[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); } printf("%d\n", f[n][m]);

    说明

    时间复杂度 = O ( 状 态 × 转 移 ) = O ( n 2 × 3 ) = O ( n 2 ) =O(状态\times 转移)=O(n^2\times 3)=O(n^2) =O(×)=O(n2×3)=O(n2)

    区间DP

    石子合并:相邻两堆石子可以合并,代价为二者石子数的和,求最小代价

    核心代码

    int s[N]; // 前缀和 int f[N][N]; for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1]; // 初始化前缀和 for (int len = 2; len <= n; len ++ ) // len=1时不合并(类似归并排序的merge) // 固定窗口大小,从小到大遍历 for (int i = 1; i + len - 1 <= n; i ++ ) { // 固定窗口左端点,则可确定窗口右端点,注意边界 int l = i, r = i + len - 1; // 窗口内划分 f[l][r] = 0x7f7f7f7; // 初始化为无穷大 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]);

    说明

    时间复杂度 O ( n 3 ) O(n^3) O(n3)

    计数类DP

    把n拆分成1~n的和的方案数(不考虑顺序)

    完全背包解法

    可以看做有 n n n种物品,第 i i i种物品的体积为 i i i,背包的容量为 n n n,每个物品可以拿无数次,求装满背包的方案数

    假设当前背包容量为 j j j,则第 i i i个物品至多装$k=\lfloor \frac{j}{i} \rfloor $个

    已知 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\left( i,j \right) =f\left( i-1,j \right) +f\left( i-1,j-i \right) +f\left( i-1,j-2i \right) +\cdots +f\left( i-1,j-ki \right) f(i,j)=f(i1,j)+f(i1,ji)+f(i1,j2i)++f(i1,jki) j < i j <i j<i时, j − i < 0 j -i < 0 ji<0 f ( i , j ) = f ( i − 1 , j ) f(i,j)=f(i-1,j) f(i,j)=f(i1,j)

    j ≥ i j\ge i ji时, j − i ≥ 0 j -i \ge 0 ji0,有 f ( i , j − i ) = f ( i − 1 , j − i ) + f ( i − 1 , j − 2 i ) + f ( i − 1 , j − 3 i ) + ⋯ + f ( i − 1 , j − k i ) f\left( i,j-i \right) =f\left( i-1,j-i \right) +f\left( i-1,j-2i \right) +f\left( i-1,j-3i \right) +\cdots +f\left( i-1,j-ki \right) f(i,ji)=f(i1,ji)+f(i1,j2i)+f(i1,j3i)++f(i1,jki) 对比可得状态转移方程 f ( i , j ) = f ( i − 1 , j ) + f ( i , j − i ) f(i,j)=f(i-1,j)+f(i,j-i) f(i,j)=f(i1,j)+f(i,ji) 综上,当 j < i j <i j<i时, f ( i , j ) = f ( i − 1 , j ) f(i,j)=f(i-1,j) f(i,j)=f(i1,j);当 j ≥ i j\ge i ji时, f ( i , j ) = f ( i − 1 , j ) + f ( i , j − i ) f(i,j)=f(i-1,j)+f(i,j-i) f(i,j)=f(i1,j)+f(i,ji)。特别的 f ( 0 , ∗ ) = 1 f(0,*)=1 f(0,)=1

    核心代码

    // 未压缩f f[0][0] = 1; for (int i = 1; i <= n; i ++) for (int j = 0; j <= n; j ++) if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod; else f[i][j] = f[i - 1][j]; cout << f[n][n] << endl; // 压缩f f[0] = 1; for (int i = 1; i <= n; i ++ ) for (int j = i; j <= n; j ++ ) f[j] = f[j] + f[j - i]; cout << f[n] << endl;

    其它算法

    j j j个数中最小值是 1 1 1,则方案数等价于去掉 1 1 1 1 1 1时的方案数 f ( i − 1 , j − 1 ) f(i-1,j-1) f(i1,j1),此时总和为 i − 1 i-1 i1,共有 j − 1 j-1 j1个数

    j j j个数中最小值 > 1 >1 >1,则方案数等价于 j j j个数全都减 1 1 1的方案数 f ( i − j , j ) f(i-j,j) f(ij,j)

    核心代码

    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;

    数位统计DP

    给定两个整数 a a a b b b,求$ a 和 和 b$之间的所有数字中 0 0 0~ 9 9 9的出现次数

    思路

    count(n, x)表示 1 1 1~ n n n中,数字 x x x出现的次数 0 ≤ x ≤ 9 0\le x \le 9 0x9

    考虑数 x x x在n=abcdefg的第 4 4 4 d d d出现的次数,不妨把 n n n看成 y y y x z z z yyyxzzz yyyxzzz

    000 ≤ y y y ≤ ( a b c − 1 ) 000 \le yyy\le (abc-1) 000yyy(abc1)时, 000 ≤ z z z ≤ 999 000\le zzz\le 999 000zzz999 x ≠ 0 x\ne 0 x=0时,此时共有 a b c × 1000 abc\times 1000 abc×1000次当 x = 0 x=0 x=0时,由于 a b c d abcd abcd不能全为 0 0 0,因此此时共有 ( a b c − 1 ) × 1000 (abc - 1)\times 1000 (abc1)×1000次 当 y y y = a b c yyy=abc yyy=abc时 当 d < x d<x d<x a b c d e f g < a b c x z z z abcdefg<abcxzzz abcdefg<abcxzzz,此时出现 0 0 0次当 d = x d=x d=x 000 ≤ y y y ≤ e f g 000\le yyy \le efg 000yyyefg,此时出现 e f g + 1 efg+1 efg+1次当 d > x d>x d>x 000 ≤ y y y ≤ 999 000\le yyy \le 999 000yyy999,此时出现 1000 1000 1000

    特殊处理

    当求的是最左边那位出现的次数时, a b c abc abc不存在,因此此时只需考虑第2种情况当 x = 0 x=0 x=0,且遍历到最左边那位时,根据上述讨论,需要把 n n n看成 x y y y z z z = 0 y y y z z z xyyyzzz=0yyyzzz xyyyzzz=0yyyzzz,这是不合法的,因此当 x = 0 x=0 x=0时,从左起第2位开始遍历

    核心代码

    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; } 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; for (int i = n - 1 - !x; i >= 0; i -- ) // 当x=0时,从左起第2位开始遍历 { // 考虑左起第1位时不存在abc,跳过 if (i < n - 1) { res += get(num, n - 1, i + 1) * power10(i); if (!x) res -= power10(i); // x=0,abc不能全为0,排除这种情况 } // 尽管左起第1位不存在abc,但存在efg,因此保留这部分 if (num[i] == x) res += get(num, i - 1, 0) + 1; else if (num[i] > x) res += power10(i); } return res; } for (int i = 0; i <= 9; i ++ ) cout << count(b, i) - count(a - 1, i) << ' '; // 类似前缀和思想

    状态压缩DP

    蒙德里安的梦想

    在给定大小的网格放入 1 × 2 1\times 2 1×2 2 × 1 2\times 1 2×1的矩形

    状态压缩是通过用二进制数表示状态实现的

    当确定横向矩形的位置后,竖向矩形的位置就确定了,因此只需考虑横向矩形的放置方法。

    j j j表示当前列的状态,它记录了上一列放入横向矩形的行号,也可理解为当前列被上一列横向矩形捅出的行号,这些行号不可用。例如10010表示上一列第1行和第4行放有横向矩形,即当前列的第1行和第4行不可用。 k k k表示上一列的状态,与 j j j类似。

    假设有 n n n行,则状态 j j j表示某列 n n n个格子的使用情况,格子被占用记为1,空闲记为0。因此这n个格子一共有 2 n 2^n 2n情况,且 0 ≤ j ≤ 2 n − 1 0\le j\le 2^n - 1 0j2n1

    集合根据上一列的状态 k k k划分,因此共有 2 n 2^n 2n种状态划分方式,当满足横向矩形不碰撞以及剩余部分能放完竖向矩形两个条件时, f ( i , j ) f(i,j) f(i,j)能转移到 f ( i − 1 , k ) f(i-1,k) f(i1,k)

    核心代码

    const int N = 12, M = 1 << N; // 最大行数,每列的最大状态数 long long f[N][M]; bool st[M]; // 穷举第i列和第i+1列能放完竖向矩形的情形(找到所有不存在连续奇数个0的情况) // 预处理,减少重复计算的代价 for (int i = 0; i < 1 << n; i ++ ) { int cnt = 0; st[i] = true; for (int j = 0; j < n; j ++ ) if (i >> j & 1) { if (cnt & 1) { st[i] = false; break; } cnt = 0; } else cnt ++ ; if (cnt & 1) st[i] = false; } f[0][0] = 1; // 全部放竖向矩形,1种方案 for (int i = 1; i <= m; i ++ ) // 遍历1~m列 for (int j = 0; j < 1 << n; j ++ ) // 穷举当前列的可能状态 for (int k = 0; k < 1 << n; k ++ ) // 穷举上一列的可能状态 if ((j & k) == 0 && st[j | k]) // 判断是否满足状态转移条件(不碰撞,能放满) f[i][j] += f[i - 1][k]; // 状态转移 cout << f[m][0] << endl; // 当放完第0~m-1列后,第m列没有捅出的横向矩形的情形就是最终结果

    说明

    时间复杂度 O ( n × 2 n × 2 n ) = O ( n 4 n ) O(n\times 2^{n} \times 2^{n})=O(n4^n) O(n×2n×2n)=O(n4n),但 n = 11 n=11 n=11,实际上只需计算 4 × 1 0 7 4\times 10^7 4×107次,能在1s内完成

    最短Hamilton路径

    给定一张 n n n 个点的带权无向图,点从 0 0 0~ n − 1 n-1 n1 标号,求起点 0 0 0 到终点 n − 1 n-1 n1 的最短Hamilton路径。 Hamilton路径的定义是从 0 0 0 n − 1 n-1 n1 不重不漏地经过每个点恰好一次。

    将f[i][j]所表示的集合中的所有路线,按倒数第二个点分成若干类,其中第k类是指倒数第二个点是k的所有路线。那么f[i][j]的值就是每一类的最小值,再取个min。而第k类的最小值就是f[i - (1 << j)][k] + w[k][j]。

    从定义出发,最后f[(1 << n) - 1][n - 1]就表示所有“经过了所有点,且最后位于点n-1的路线”的长度的最小值,也就是我们要求的答案。

    核心代码

    memset(f, 0x3f, sizeof f); // 初始化为无穷大 f[1][0] = 0; // 表示只有起点0且最后位于起点0的路线的长度是0,此时点集i的最后一位是1,其余为0,因为点集只有起点0,故i=1 for (int i = 0; i < 1 << n; i ++ ) // 穷举所有可能的点集 for (int j = 0; j < n; j ++ ) // 从当前点集找一个点(二进制串中位为1的位置) if (i >> j & 1) for (int k = 0; k < n; k ++ ) // 从当前点集找另外一个点(可以和之前找的相同) if (i >> k & 1) f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); // 尝试从后找的点到达点j cout << f[(1 << n) - 1][n - 1]; // 所有点都在点集,且终点是n-1

    树形DP

    给定一个带结点值的树,求一个结点集合,使得集合里任意两个结点都不相邻,且结点值的和最大

    根据有无上司划分集合

    若上司存在,则不考虑所有直接下属,只考虑所有间接下属若上司存在,则考虑直接下属,在有无下属中选择幸福值最大的那个方案

    核心代码

    int n; int h[N], e[N], ne[N], idx; int happy[N]; int f[N][2]; 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; i = ne[i]) { int j = e[i]; // 子结点 dfs(j); // 递归子结点 // 状态转移 f[u][1] += f[j][0]; f[u][0] += max(f[j][0], f[j][1]); } } // 核心 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]));

    说明

    使用邻接表表示树DFS+动态规划

    记忆化搜索

    给一个矩阵,求一条路径,使得它的长度最长,且路径上的值是递减的。(只能往上下左右移动)

    记忆化搜索指保存中间结果,避免重复计算,用空间换时间

    核心代码

    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) { if (f[x][y] != -1) return f[x][y]; // 已经计算过,不必重复计算(记忆化搜索) f[x][y] = 1; for (int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; if (g[a][b] < g[x][y]) f[x][y] = max(f[x][y], dfs(a, b) + 1); } return f[x][y]; } memset(g, 0x3f, sizeof g); // 边界为无穷大,不能滑到,可以省去边界判断 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));

    P.S. 如果大家有兴趣,可以去Acwing《算法基础课》看看 我在Acwing也分享了一份,欢迎去围观

    Processed: 0.035, SQL: 9