//    pos    = 当前处理的位置(一般从高位到低位)

//    pre    = 上一个位的数字(更高的那一位)

//    status = 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回,

//         　　 给计数器+1。

//    limit  = 是否受限,也即当前处理这位能否随便取值。如567,当前处理6这位,

//         　　 如果前面取的是4,则当前这位可以取0-9。如果前面取的5,那么当前

//         　　 这位就不能随便取，不然会超出这个数的范围,所以如果前面取5的

//         　　 话此时的limit=1,也就是说当前只可以取0-6。

//

//    用DP数组保存这三个状态是因为往后转移的时候会遇到很多重复的情况。

int    dfs(int pos,int pre,int status,int limit)

{

    //已结搜到尽头,返回"是否找到了答案"这个状态。

    if(pos < )

        return    status;

    //DP里保存的是完整的,也即不受限的答案,所以如果满足的话,可以直接返回。

    if(!limit && DP[pos][pre][status] != -)

        return    DP[pos][pre][status];

    int    end = limit ? DIG[pos] : ;

    int    ret = ;

    //往下搜的状态表示的很巧妙,status用||是因为如果前面找到了答案那么后面

    //还有没有答案都无所谓了。而limti用&&是因为只有前面受限、当前受限才能

    //推出下一步也受限，比如567,如果是46X的情况,虽然6已经到尽头,但是后面的

    //个位仍然可以随便取,因为百位没受限,所以如果个位要受限,那么前面必须是56。

    //

    //这里用"不要49"一题来做例子。

    for(int i = ;i <= end;i ++)

        ret += dfs(pos - ,i,status || (pre ==  && i == ),limit && (i == end));

    //DP里保存完整的、取到尽头的数据

    if(!limit)

        DP[pos][pre][status] = ret;

    return    ret;

}