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 200
long 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 位，当前奇数位和减偶数位和为 diff，tight 表示是否贴着上界，started 表示是否已开始填数字。
· 前导零处理：started=0 时可以选择跳过当前位，或者从 1 开始填数字，避免将前导零误判为偶数位。
· 奇偶判断：pos%2==0 视为奇数位（从0开始索引），加 d；否则为偶数位，减 d。
· 区间转换：用 count_upto(high) - count_upto(low-1) 计算 [low, high] 内的平衡数个数。