通过先前在《动态规划——背包问题》中关于动态规划的初探，我们其实可以看到，动态规划其实不是像凸包、扩展欧几里得等是具体的算法，而是一种在解决问题中决策的思想。在不同的题目中，我们都需要根据题设恰到好处的把整个过程分割成小的状态，然后找到对应的状态转移方程，尽管都是这个过程，但是有时候条件稍微一遍，我们分析状态并找状态转移方程的思路都会发生改变，因此动态规划的题目呈现出很大的灵活性。
除了典型那背包问题涉及动态规划，还有很多其他的模型——概率dp、数位dp、区间dp、插头dp，这些都是在不同的情景中利用动态规划的思想来解决的具体模型，在接下来的文章中，笔者将一一介绍。
直接通过题目来学习数位dp。(Problem source : Light OJ 1122)
Description
Given a set of digits S, and an integer n, you have to find how many n-digit integers are there, which contain digits that belong to S and the difference between any two adjacent digits is not more than two.
Input
Input starts with an integer T (≤ 300), denoting the number of test cases.
Each case contains two integers, m (1 ≤ m < 10) and n (1 ≤ n ≤ 10). The next line will contain m integers (from 1 to 9) separated by spaces. These integers form the set S as described above. These integers will be distinct and given in ascending order.
Output
For each case, print the case number and the number of valid n-digit integers in a single line.
题目大意：给出一个数组S，和一个整数n，需要你计算用数组S中的数组成一个长度为n的整数，要求这个整数相邻两位的差要小于2。
数理分析：所谓好的开始是成功过的一半，动态规划问题的解决往往也是起始于好的dp数组的定义，这个dp数组用来记录各个状态的值。类似含有n种物体的背包问题，在这里我们需要排n位数字，显然从第1位开始，一直构造到第n位。可以说，这是dp数组的一个维度了，可以表征一种状态。我们在想，在这种状态下，整个问题还可以分解成哪些状态，我们从第i位(从后往前构造，即：最高位)放的数入手，它可以是序列S中的任意一个数字，这又是dp数组的一个维度了。
因此我们可以设置数组dp[i][j]，表示i位整数，且最高位上的整数是j的个数。那么我们容易看到，状态转移方程为：
dp[i][j] = dp[i-1][j-2] + dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2]。
基于状态转移方程的给出，我们就可以很容易变成实现了。
参考代码如下。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int m,n,ans;
bool a[];
int dp[][];
void init()
{
memset(dp,,sizeof(dp));
for(int i=;i<=;i++)
if(a[i]) dp[][i]=;
}
void solve()
{
for(int i=;i<=n;i++)
for(int j=;j<=;j++)
if(a[j]){
for(int k=j-;k<=j+;k++)
if(k>=&&k<=)
dp[i][j]+=dp[i-][k];
}
ans=;
for(int i=;i<=;i++)
ans+=dp[n][i];
}
int main()
{
int T,t,i,x,j;
int temp;
cin>>T;
for(j=;j<=T;j++)
{
cin>>m>>n;
memset(a,false,sizeof(a));
for(i=;i<=m;i++)
{
cin>>temp;
a[temp]=;
}
init();
solve();
printf("Case %d: %d\n",j,ans);
}
return ;
}
我们早来看一道有关数位dp的问题。(Problem source : hdu 2089)
题意似乎简单暴力，然是如果真得用暴力来解决问题的话会非常费时的，因此我们这里讨论如何利用动态规划的思想来求解。
从题目的限制条件我们不难看出，我们需要从位的角度来看十进制整数。动态规划除了能够动态保存最优解，另一大作用便是将全局性的问题给子问题化。
我们依然从整个过程的中间开始，对于一个i位整数a，在区间[0,a]上满足题设限制的整数的个数是f(a),那么对于一个i-1位的整数b,在区间[0,b]上满足题设限制的整数的个数是f(b)，那么f(a)和f(b)是否有着什么联系呢？如果有的话，我们就找到了递推关系，也就是状态转移方程，便能够将全局问题给子问题化了。
那么下面我们来看看f(a)和f(b)有着怎样的递推关系，这其实有些类似组合数学方面的问题，如果学习过错排的读者可能会感触更深。我们假设i位的整数的最高位是k，那么显然对于f()函数就有了第二维的限制，那么我们在这里设置dp[i][j]来表示0到最高位是j的i位整数满足条件的整数个数。那么结合简单的组合数学的思想，我们可以看到如下的递推关系。
dp[i][j] = ∑dp[i-1][k] ， 其中k∈[1,9]。
基于dp[][]的得到，我们要求0到某个具体的数字x(注意dp数组表征的并不是某个具体数字)x范围内满足限制的整数个数，只需从该数字的最高位开始按位依次往下记录数据即可。有读者可能会问，为何不从最低位开始呢？我们看到，从高位往低位记录，我们控制当前位的数字小于x对应位的数字，这样保证我们构造的数处在[0,x)内，而如果从低位往高位记录，那记录的末了就非常难以控制当前构造的数字是否在[0,x)的范围内。而正是基于这个特点，我们通过这种方法得到是[0,x)范围内的解，而显然题设想让我们找到[l,r]范围内的解，在这里我们容易想到，可以通过一个中间量来嫁接一下，[l,r]上的解其实就是[0,r]上的解减掉[0 , l - 1]上的解。如果设Fun作为求解的函数，基于Fun(0,x)函数其实求的是[0,x)上的解，记录F[l,r]表示[l,r]上的解，那么则有F[l,r] = Fun(0,r+1) - Fun(0,l)。
其实概括地来看上面的分析过程不难发现，对于数位dp的求解，相对于背包问题，这种模型并没用用动态规划来求解什么最优解，而是利用这种思想通过预处理来将问题子化，并保存子问题的解，然后对于输入不同的值，再来通过子问题间不同的组合来解决问题。
参考代码如下。
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[][];
void init()
{
memset(dp,,sizeof(dp));
dp[][] = ;
for(int i=;i<=;i++)
{
for(int j=;j<;j++)//枚举第i位可能出现的数
{
for(int k=;k<;k++)//枚举第i-1位可能出现的数
{
if(j!=&&!(j==&&k==))
dp[i][j] += dp[i-][k];
}
}
}
}
int solve(int n)
{
init();
int digit[];
int len = ;
while(n>)
{
digit[++len] = n%;
n/=;
}
digit[len+]=; //为下面判断最大数位是否含62做个预处理
int ans = ;
for(int i=len;i;i--)
{
for(int j=;j<digit[i];j++)//这里一定要是小于而不是小于等于，至于理由读者可以简单的思考一下
{
if(j!=&&!(digit[i+]==&&j==))
ans+=dp[i][j];
}
if(digit[i]==||(digit[i]==&&digit[i+]==))
break;
}
return ans;
}
int main()
{
int l,r;
while(cin>>l>>r)
{
if(l== && r == )
break;
else
cout<<solve(r+) - solve(l)<<endl;
}
return ; }