Python 输入正整数n,输出小于或等于n且各位数字均不含4的整数的总数
时间: 2024-05-08 22:16:03 浏览: 10
可以用数位DP(动态规划)求解。
定义dp[i][0/1]表示当前处理到第 i 位,且前 i 位是否已经和 n 的对应位匹配(即前 i 位是否已经等于 n 的前 i 位)的数字中,不含 4 的数字的总数。
具体地,dp[i][0] 表示当前处理的数字已经小于 n 前 i 位,dp[i][1] 表示当前处理的数字已经等于 n 前 i 位。对于每一位数字,可以枚举当前位填入的数字为 0~9,但需要排除数字 4,因为题目要求不含 4 的数字。
因此,可以用下面的状态转移方程来更新 dp 值:
dp[i][0] = dp[i][0] + dp[i-1][0] * 8 + dp[i-1][1] * (num[i]-1)
dp[i][1] = dp[i][1] + dp[i-1][1] * (num[i]==4 ? 0 : 1)
其中,num[i] 表示 n 的第 i 位数字,乘以 8 的原因是当前位可以填入 0~9 中除了 4 的 8 种数字。
最终答案即为 dp[len(num)][0]+dp[len(num)][1]。
代码如下:
```
n = int(input())
num = list(map(int, str(n)))
dp = [[0]*2 for _ in range(len(num)+1)]
dp[0][1] = 1
for i in range(1, len(num)+1):
for j in range(10):
if j == 4:
continue
if j < num[i-1]:
dp[i][0] += dp[i-1][0] * 8 + dp[i-1][1]
elif j == num[i-1]:
dp[i][0] += dp[i-1][0]
dp[i][1] += dp[i-1][1]
else:
dp[i][0] += dp[i-1][0] * 8
dp[i][1] += dp[i-1][1] * (j!=4)
print(dp[len(num)][0] + dp[len(num)][1])
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)