给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。这个题用数位dp如何写
时间: 2024-04-15 11:31:35 浏览: 23
对于这个题目,可以使用数位 DP 的思想进行求解。以下是一个使用数位 DP 解决计算整数中数字 1 出现个数的示例代码:
```python
def countDigitOne(n):
if n <= 0:
return 0
num = str(n)
length = len(num)
dp = [0] * length
dp[0] = int(num[0]) >= 1
for i in range(1, length):
if int(num[i]) >= 1:
dp[i] += dp[i-1] + int(num[:i]) * pow(10, length-i-1)
else:
dp[i] += dp[i-1]
return dp[-1] + 1
n = 13
count = countDigitOne(n)
print(count)
```
在这个示例代码中,我们首先将整数 n 转换为字符串,并获取它的长度。然后创建一个长度为 n 的数组 dp,用于记录每一位数字 1 出现的次数。
接下来进行数位 DP 的计算,从最高位开始遍历到最低位。对于每一位 i:
- 如果当前数字大于等于 1,那么该位数字 1 出现的次数为 dp[i-1](前面的数字出现的次数)加上当前位之前的数字(即 num[:i])乘以 10 的 (length-i-1) 次幂。
- 如果当前数字等于 0,那么该位数字 1 出现的次数只需等于 dp[i-1]。
最后,将 dp 数组的最后一个元素(即总的数字 1 出现的次数)加上 1,即为所求的结果。
对于输入 n = 13,运行示例代码得到的结果为 6,表示小于等于 13 的非负整数中数字 1 出现的次数为 6。