数位DP新识

简单题：HDU2089    HDU3652  HDU4734   HDU3555  POJ3252  HigoCoder1033(需要前导0，或者用方法4)

总结：

1，dfs(pos,state,limit,begin_zero)    只是大概方程，根据不同的条件有不同的限制。

2，减少memset可以时间上优化，但是得用limit限制。

3，前导0特殊关注，有时需要，有时不需要。

4，懒得判前导0，可以从后面向前面枚举，但是memset的后果是时间会浪费一些

    cnt=0;ans=0;
    while(v){
        a[++cnt]=v%10;
        v/=10;
    }
    for(i=1;i<=pos;i++){
        memset(dp,0,sizeof(dp));
        ans+=dfs(i,state,i==pos);
    }

5,数位DP可以抽象为树形DP，dp[pos][state]保存的是以pos为节点的子树在state状态下的结果。

通过后序遍历，我们能得到后面的访问的state是否满足要求。在遇到叶子节点的时候来判断是否满足，从而把结果向上传递。

（以‘49’一题为例：）

LL _dfs(int pos,bool limit,bool pre,bool stat)
{
     if(pos==0) return stat;  //访问到叶子，state为真返回1，否则返回0
     LL tmp=0;      //tmp保存子树的结果，最后传给dp
     if(!limit&&dp[pos][limit][pre][stat]) return dp[pos][limit][pre][stat];   //在没有limit限制时可以用记忆化值
     int Up=limit?a[pos]:9;   //上界
     for(int i=0;i<=Up;i++)
         tmp+=_dfs(pos-1,limit&&i==Up,i==4,stat||(pre&&i==9));    //后序遍历
     dp[pos][limit][pre][stat]=tmp;    //得到子树的结果
     if(tmp>ans) ans=tmp; 
     return tmp;     //向上传递
}