算法思路：

感觉dfs版的数位dp还是挺简单的，直接dp然后递推统计答案的那种比它搞脑子多了。

在dfs版本中，我们需要特别注意的地方有两个：

1、是否贴上界：

这是个啥呢？

很简单，给大家举个栗子，假如我们要求解1-12345这段区间，如果我们已经做了3位，而前三位正好是123，那么我们第4位就只能取0-5，否则我们就可以取0-9。

2、有没有前导零：

这有为啥要特殊记呢？

因为前导零会影响我们对合法方案的统计。

当现在的状态有前导零，或者贴上界的时候我们就不能记忆化，因为它们是与别的状态不同的，不同之处就是上面讲的那些啦。

dfs模板：

function dfs(pos,...,lead,flag:Longint):int64;var    res:int64;    i,limit:Longint;begin     //pos：当前在做第几位。     //lead：0/1 有/没有 前导零     //flag：0/1 是/否   贴上界    if pos>len then exit(...);    ......    ......                           //各种优化    if (dp[pos][...]<>-1)and(lead+flag=0) then exit(dp[pos][...]);          //记忆化    if flag=1 then limit:=a[len-pos+1] else limit:=9;                       //最高枚举到几    res:=0;    for i:=0 to limit do        res:=res+dfs(pos+1,...,...,ord((lead=1)and(i=0)),ord((flag=1)and(i=limit)));    if lead+flag=0 then dp[pos][...]:=res;    dfs:=res;end;function part(x:int64):int64;            //数位分离begin    len:=0; part:=0;while x>0 do        begin inc(len); a[len]:=x mod 10; x:=x div 10; end;     part:=dfs(1,...,1,1);end;

转载于:https://www.cnblogs.com/WR-Eternity/p/9928602.html

你可能感兴趣的文章