首先递推公式：

dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];  // 不含49

dp[i][1] = dp[i-1][0];  // 不含49以9开头

dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; 

// 含49

 

然后从高位往低位递推，ans+=dp[i][2]*num[i]，指i位的方案数。如果前面有49，那么ans可以再+=dp[i][0]*num[i]。否则如果该位比4大，那么可以加上dp[i][1]；最后如果前一位4该位为9则可以更新有没有49。

代码：

1 #include
       
         2 #include
        
          3 long long dp[25][5]; 4 int num[25]; 5 int main() 6 { 7     long long ans,x; 8     int T,last,flag,cnt,i; 9     memset(dp,0,sizeof(dp));10     dp[0][0]=1;11     for (i=1;i<=20;i++)12     {13         dp[i][2]=dp[i-1][2]*10+dp[i-1][1];14         dp[i][1]=dp[i-1][0];15         dp[i][0]=dp[i-1][0]*10-dp[i-1][1];16     }17     scanf("%d",&T);18     while (T--)19     {20         scanf("%I64d",&x);21         x++;22         cnt=ans=flag=last=0;23         while (x!=0){24             num[++cnt]=x%10;25             x=x/10;26         }27         for (i=cnt;i>=1;i--)28         {29             ans+=dp[i-1][2]*num[i];30             if (flag)31                 ans+=dp[i-1][0]*num[i];32             if (!flag&&num[i]>4)33                 ans+=dp[i-1][1];34             if (last==4&&num[i]==9)35                 flag=1;36             last=num[i];37         }38         printf("%I64d\n",ans);39     }40 }
        
       

 另外不用递推式，直接递归的写法：

1 #include
       
         2 #include
        
          3 long long dp[25][15][2]; 4 int num[25]; 5 long long dfs(int pos,int pre,int flag,int limit) 6 { 7     int tmp,i; 8     long long ans=0; 9     if (pos==0) return flag;10     if (!limit&&dp[pos][pre][flag]!=-1)11         return dp[pos][pre][flag];12     tmp=limit?num[pos]:9;13     for (i=0;i<=tmp;i++)14         ans+=dfs(pos-1,i,flag||(pre==4&&i==9),limit&&(i==tmp));15     if (!limit)16         dp[pos][pre][flag]=ans;17     return ans;18 }19 int main()20 {21     int T,cnt;22     long long x;23     scanf("%d",&T);24     while (T--)25     {26         scanf("%I64d",&x);27         memset(dp,-1,sizeof(dp));28         cnt=0;29         while (x!=0){30             num[++cnt]=x%10;31             x/=10;32         }33         printf("%I64d\n",dfs(cnt,0,0,1));34     }35 }
        
       

 题目链接：