DeepSeek LeetCode 3971. 最大总价值 C语言实现

根据您提供的函数签名这对应的是LeetCode 3791「给定范围内平衡整数的数目」而非 3971。平衡整数定义为奇数位数字之和等于偶数位数字之和。核心解法是数位 DP用前缀和思想将区间 [low, high] 转化为 count(high) - count(low - 1)。下面是 C 语言实现c#include string.h#include stdlib.h// 记忆化数组dp[pos][diff][tight][started]// 由于 diff 范围 [-9*18, 9*18]加上偏移量 OFFSET 转为非负索引#define MAX_POS 20#define MAX_DIFF 200long long memo[MAX_POS][MAX_DIFF][2][2];char digits[MAX_POS];int len;long long dfs(int pos, int diff, int tight, int started) {if (pos len) {return (started diff 0) ? 1 : 0; // 必须已经开始且差值为0[reference:4]}if (memo[pos][diff 100][tight][started] ! -1) {return memo[pos][diff 100][tight][started];}long long res 0;int limit tight ? (digits[pos] - 0) : 9;// 情况1还没开始跳过当前位前导零if (!started) {res dfs(pos 1, diff, 0, 0); // tight 变为 false[reference:5]}// 情况2枚举当前位可填数字int start_digit started ? 0 : 1; // 未开始则不能填0[reference:6]for (int d start_digit; d limit; d) {int new_diff diff ((pos % 2 0) ? d : -d); // 奇数位加偶数位减[reference:7]int next_tight tight (d limit);res dfs(pos 1, new_diff, next_tight, 1);}memo[pos][diff 100][tight][started] res;return res;}long long count_upto(long long n) {if (n 10) return 0; // 平衡数至少需要两位数[reference:8]sprintf(digits, %lld, n);len strlen(digits);// 初始化记忆化数组for (int i 0; i MAX_POS; i) {for (int j 0; j MAX_DIFF; j) {for (int t 0; t 2; t) {for (int s 0; s 2; s) {memo[i][j][t][s] -1;}}}}return dfs(0, 0, 1, 0); // 从最高位开始初始受限未开始[reference:9]}long long countBalanced(long long low, long long high) {return count_upto(high) - count_upto(low - 1); // 前缀和相减[reference:10]}核心逻辑说明· 数位 DP 状态dfs(pos, diff, tight, started) 表示处理到第 pos 位当前奇数位和减偶数位和为 difftight 表示是否贴着上界started 表示是否已开始填数字。· 前导零处理started0 时可以选择跳过当前位或者从 1 开始填数字避免将前导零误判为偶数位。· 奇偶判断pos%20 视为奇数位从0开始索引加 d否则为偶数位减 d。· 区间转换用 count_upto(high) - count_upto(low-1) 计算 [low, high] 内的平衡数个数。