千问 LeetCode 2920. 收集所有金币可获得的最大积分 C语言实现

这道题的 C 语言解法，核心思路与 Java 版本完全一致，都是采用树形动态规划（Tree DP）结合记忆化搜索。由于 C 语言没有现成的集合与动态数组库，我们需要手动使用邻接表来建树，并自行管理内存。

以下是完整的 C 语言实现：

💻 C 语言代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义邻接表节点
typedef struct Node {
int val;
struct Node* next;
} Node;

// 创建新的邻接表节点
Node* createNode(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->val = val;
newNode->next = NULL;
return newNode;
}

// 深度优先搜索（记忆化递归）
int dfs(int i, int j, int father, int** memo, Node** graph, int* coins, int k) {
// 如果该状态已经计算过，直接返回
if (memo[i][j] != -1) {
return memo[i][j];
}

// 当前节点 i 在经过 j 次减半后的实际金币数
int currentCoin = coins[i] >> j;

// 策略1：使用方式1收集 (coins[i] >> j) - k
int res1 = currentCoin - k;

// 策略2：使用方式2收集 (coins[i] >> j) / 2
int res2 = currentCoin >> 1;

// 遍历所有子节点（排除父节点）
Node* cur = graph[i];
while (cur != NULL) {
int child = cur->val;
if (child != father) {
// 累加策略1下，子树的收益
res1 += dfs(child, j, i, memo, graph, coins, k);

// 累加策略2下，子树的收益
// 剪枝：如果 j >= 13，说明再右移一次金币肯定为0，没必要继续深入递归计算 res2
if (j < 13) {
res2 += dfs(child, j + 1, i, memo, graph, coins, k);
}
}
cur = cur->next;
}

// 记录并返回最大值
memo[i][j] = (res1 > res2) ? res1 : res2;
return memo[i][j];
}

int maximumPoints(int** edges, int edgesSize, int* edgesColSize, int* coins, int coinsSize, int k) {
int n = coinsSize;

// 1. 构建邻接表表示树
Node** graph = (Node**)malloc(n * sizeof(Node*));
for (int i = 0; i < n; i++) {
graph[i] = NULL;
}

for (int i = 0; i < edgesSize; i++) {
int x = edges[i][0];
int y = edges[i][1];
// 无向图，双向添加边
Node* nodeY = createNode(y);
nodeY->next = graph[x];
graph[x] = nodeY;

Node* nodeX = createNode(x);
nodeX->next = graph[y];
graph[y] = nodeX;
}

// 2. 初始化记忆化数组 memo[i][j]
int** memo = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
memo[i] = (int*)malloc(14 * sizeof(int)); // j 最大取 14 即可
for (int j = 0; j < 14; j++) {
memo[i][j] = -1; // -1 表示未计算过
}
}

// 3. 从根节点 0 开始 DFS，初始父节点为 -1，初始减半次数为 0
int result = dfs(0, 0, -1, memo, graph, coins, k);

// 4. 释放内存
// 释放邻接表
for (int i = 0; i < n; i++) {
Node* cur = graph[i];
while (cur != NULL) {
Node* temp = cur;
cur = cur->next;
free(temp);
}
}
free(graph);

// 释放记忆化数组
for (int i = 0; i < n; i++) {
free(memo[i]);
}
free(memo);

return result;
}

📊 复杂度分析
* 时间复杂度：O(N)。虽然引入了状态 j，但因为金币最多减半 14 次就会变成 0，状态总数被限制在 N times 14 以内，每个状态只计算一次。
* 空间复杂度：O(N)。用于存储邻接表、记忆化数组以及递归调用的系统栈空间。

⚠️ C 语言实现注意事项
1. 手动建树：C 语言中没有 ArrayList，我们使用了结构体 Node 配合指针来构建邻接表（链式前向星或单链表均可）。
2. 内存管理：在 C 语言中，使用 malloc 分配的二维数组和链表节点，在函数返回前必须手动 free 释放，否则会导致内存泄漏。
3. 位运算：>> 右移运算在 C 语言中对于非负整数等同于除以 2 的幂，且效率更高。
4. 边界剪枝：依然保留了 if (j < 13) 的剪枝逻辑，防止无意义的递归调用。