gpt-3.5-turbo-0613· openai
Suzhen/CodeChat
写一个数位dp代码
- User
写一个数位dp代码
- Assistant
下面是一个典型的数位dp的代码示例,用来计算一个数的每一位之和等于一个给定的目标值的所有可能性的个数:
def count_digit_sum(n, target): # 将整数 n 转化为字符串 n_str = str(n) length = len(n_str) # 定义dp数组 # dp[i][j][k] 表示前i位数位和为j,且长度为i时的所有可能性的个数, # k = 0 表示已经达到了上界,k = 1 表示还未达到上界 dp = [[[0, 0] for _ in range(target + 1)] for _ in range(length+1)] # 初始化边界条件 dp[0][0][1] = 1 # 动态规划 for i in range(1, length+1): digit = int(n_str[i-1]) for j in range(target+1): for k in range(2): # 如果当前数位 k = 0 ,表示已经达到上界,那么下一位的数位和也必须为0 if k == 0: dp[i][j][k] += dp[i-1][j][k] else: # 遍历当前数位可取的值 for d in range(10): if d > digit: break # 如果下一位的和超过目标值,则当前数位可以取0到digit if j + d > target: break # 如果digit最大,那么下一位的数位和只能为j+d(此时k=0) if d == digit: dp[i][j][k] += dp[i-1][j+d][0] # 如果digit不是最大,那么下一位的数位和可以为j+d(k=0)或者j+d(k=1) else: dp[i][j][k] += dp[i-1][j+d][0] + dp[i-1][j+d][1] # 返回所有数位和等于target的可能性的个数 return dp[length][target][0] + dp[length][target][1] # 测试用例 n = 1234 target = 7 print(count_digit_sum(n, target)) n = 456789 target = 30 print(count_digit_sum(n, target))这个数位dp的代码的时间复杂度是O(logN * target),其中N为输入整数的长度,target为目标数位和。