[a,b]不包含49的数的个数

https://blog.csdn.net/weixin_43701790/article/details/98379811

---

以1234为例，s=[1,2,3,4]

将区间1 ~ 581按上限拆开，分成1 ~ 499（百位数字小于5）、500 ~ 579（百位为5，十位数字小于8）、580（百位为5，十位是8，个位小于1）和581分成四个部分，以次计算每一个区间求和即可。（注意，581实际在for循环中不会处理，要在for循环后面补一个判断"49"）

初始化

f 代表前面[0,i-1]位有没有49，res计算49的个数

dp[i][0] 不含49且开头不是9
dp[i][1] 不含49且开头是9
dp[i][2] 含49

dp[0][0]=1
# dp[1][0]=9
# dp[1][1]=1

for i in range(1,65):
    # 8是因为首位不能是4或者9
    dp[i][0]=int(dp[i-1][0])*9+int(dp[i-1][1])*8
    dp[i][1]=int(dp[i-1][1])+int(dp[i-1][0])
    dp[i][2]=int(dp[i-1][2])*10+int(dp[i-1][1])

dfs判断

以第i位对应的s[i]=a为例：

无论s[i]，f的值如何如果第i位取[0,a-1]，那么不受限情况下，res+=dp[len-i][2]*a。

如果第i位取a，那么受限情况下，res+=dp[len-i][2]，如果a>4，那么还得加上右侧头部为9的情况即 res+=dp[len-i][1]（如果 a==9，而且前面的第i-1位是4，那么f=true）

剩下的部分默认前面的位都取到了上限(比如1234->1xyz，12xy)，因为第一位为0的已经dp得到所有解了。所以后面只要解决分拆后的12xy即可。

# 暴力法用于验证
def bloom(n):
    counts=0
    for i in range(int(n)+1):
        if "49" in str(i):
            counts+=1
    return counts
# 数值dp
def dfs(n,dp):
    # res记录各个位49的个数
    res=0
    # 记录之前的i位是否有49
    f=False
    for i in range(len(n)):
        res+=int(n[i])*dp[len(n)-1-i][2]
        if f:
            res+=(dp[len(n)-1-i][1]+dp[len(n)-1-i][0])*(int(n[i]))
            # 坚持不求各位上的上界最大值 1234->12xx不求，只求11xx,10xx
        elif n[i]>"4":
            # 58 -> 49 上界大于4当然可以有49
            res+=dp[len(n)-1-i][1]
        # elif n[i]=="4":
        # 坚持不求各位上的上界最大值
        #     if i+1<len(n) and n[i+1]=="9":
        #         res+=dp[len(n)-1-i][1]
        if n[i]=="9" and (i-1>=0 and n[i-1]=="4"):
            f=True
    if "49" in n:
        res+=1
    return res

# dp[i][0] 不含49且开头不是9
# dp[i][1] 不含49且开头是9
# dp[i][2] 含49
dp=[]
for i in range(65):
    dp.append([0,0,0])

dp[0][0]=1
# dp[1][0]=9
# dp[1][1]=1

for i in range(1,65):
    # 8是因为首位不能是4或者9
    dp[i][0]=int(dp[i-1][0])*9+int(dp[i-1][1])*8
    dp[i][1]=int(dp[i-1][1])+int(dp[i-1][0])
    dp[i][2]=int(dp[i-1][2])*10+int(dp[i-1][1])

n="49419"

print(dfs(n,dp),bloom(n))