数位DP
计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…
#include<bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
scanf("%d%s",&n, a + 1);
scanf("%d%s",&m, b + 1);
for(int i=0;i<=m;i++) f[0][i] = i;
for(int i=0;i<=n;i++) f[i][0] = 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);
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]);
return 0;
}
状态压缩类DP
整数划分
求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。
例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。
思路：所谓的状态压缩DP，就是用二进制数保存状态。为什么不直接用数组记录呢？因为用一个二进制数记录方便作位运算。前面做过的八皇后，八数码，也用到了状态压缩。本题等价于找到所有横放 1 X 2 小方格的方案数，因为所有横放确定了，那么竖放方案是唯一的。用f[i][j]记录第i列第j个状态。j状态位等于1表示上一列有横放格子，本列有格子捅出来。转移方程很简单，本列的每一个状态都由上列所有“合法”状态转移过来f[i][j] += f[i - 1][k]
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 12, M = 1 << N;
int n,m;
long long f[N][M];// 第一维表示列， 第二维表示所有可能的状态
bool st[M];//存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。
int main(){
while(cin >> n >> m, n | m){ //读入n和m，并且不是两个0即合法输入就继续读入
memset(f, 0, sizeof f);
//第一部分：预处理1
//对于每种状态，先预处理每列不能有奇数个连续的0
for(int i = 0; i < (1 << n); i++){
st[i] = true; // 某种状态没有奇数个连续的0则标记为true
int cnt = 0; // 记录连续的0的个数
for(int j = 0; j < n; j++){ //遍历这一列，从上到下
if(i >> j & 1){
// i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位
// &1为判断该位是否为1，如果为1进入if
if(cnt & 1) st[i] = false; //这一位为1，看前面连续的0的个数，如果是奇数（cnt&1为真）则该状态不合法
cnt = 0;
}
else cnt++;
}
if(cnt & 1) st[i] = false;
}
f[0][0] = 1;
for(int i = 1; i <= m; i++)
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;
}
return 0;
}
