由本题思考到dp问题的几种状态类型：
对于数据保存在数组a[n]，求解关于这n个数的相关的最优解或计数问题.
（1）线性dp，每个状态表示为一个下标i（或者说是一个固定起点的区间[0, i]）（可以说是起点固定的区间dp）
（2）区间dp，每个状态表示为一个区间[i, j];（枚举的过程考虑的整个区间的所有组合情况(区间组合的顺序)。）
（3）状态压缩dp（集合上的dp），每个状态表示一个多个元素的集合。（枚举的过程可考虑到集合所有点的全排列情况（点的排列顺序））（与前面不同的是，元素之间没有特定小标的位置要求）
而集合表示的含义，根据具体问题有可有不同的意思。
1）即简单的集合的含义。
2） 最优匹配对的问题。每个集合表示集合中所有点所能构成的最有匹配问题。
3）集合的所有元素的全排列情况
tsp问题。每个集合表示的是集合中所有点的全排列之后，得到的路径的最优路径值。
本题。和tsp问题类似。每个集合表示的是集合中所有点的全排列之后，能到的所有数字的取模值。
各种状态的具体含义，根据具体问题有可有不同的意思。
cf235 div2, D Roman and Numbers（状态压缩dp）
下面几乎是本场cf第一名的解法
本题题意：给定数字n（10e18以内）和m（100以内），数字的各位重新排列后得到的能被m整除的数的个数.
（1）即18个数（0~9）（包含重复的数子），组成的所有排列数字能被m整数的数的个数
共18！种情况，优化是必须的。最后在用的是集合状态表示，每个集合表示的含义是，所有元素的全排列的模的情况，所以状态压缩。
（2）尤其注意判重的方法：保证对于同一个串数，只在其后面添加不重复的数字。！！！
//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)
typedef long long LL;
const int INF = 1000000007;
const double eps = 1e-10;
const int maxn = 550010;
int n, m;
LL dp[1 << 18][100];
vector<int>a;
int main ()
{
char s[20];
cin >> s >> m;
int n = strlen(s);
for (int i = 0; i < n; i++) a.push_back(s[i] - ‘0‘);
sort(a.begin(), a.end());///!!!
int ALL = (1 << n) - 1;
dp[0][0] = 1;
for (int r = 0; r <= ALL; r++)
for (int i = 0; i < m; i++) if (dp[r][i])
{
int x = i * 10;///将下个数插到最后!!!
int pre = -1;
for (int j = 0; j < n; j++) if (!(r & (1 << j)))
{
if ((r == 0 && a[j] == 0) || (a[j] == pre)) continue;///保证首位不为0且不重复!!!
int nowx = (x + a[j]) % m;
pre = a[j];
dp[r | (1 << j)][nowx] += dp[r][i];
// cout << nowx << ‘ ‘ << dp[r][i] << ‘ ‘ << dp[r | (1 << j)][nowx] << endl;
}
}
cout << dp[ALL][0] << endl;
return 0;
}
/**
（1）重复的问题
（2）与背包的结合
（3）0-1和完全的区别
*/cf235，D Roman and Numbers（状态压缩dp）引发对dp中几种状态类型的思考,布布扣,bubuko.com
cf235，D Roman and Numbers（状态压缩dp）引发对dp中几种状态类型的思考
原文：http://blog.csdn.net/guognib/article/details/21647461