当前位置：首页 > article >正文

Leecode刷题C语言之从栈中取出K个硬币的最大面积和

article 2025/1/23 11:24:56

执行结果:通过

执行用时和内存消耗如下：

#define max(a, b)   ((a) > (b) ? (a) : (b))
#define min(a, b)   ((a) < (b) ? (a) : (b))

int maxValueOfCoins(int** piles, int pilesSize, int* pilesColSize, int k){
    int dp[k + 1], tdp[k + 1];
    int i, j, p, q, ans = 0;
    memset(dp, 0, sizeof(int) * (k + 1));

    for (i = 1; i <= pilesSize; i++) {
        for (j = 1; j < pilesColSize[i - 1]; j++) {
            piles[i - 1][j] += piles[i - 1][j - 1];
        }
        memcpy(tdp, dp, sizeof(int) * (k + 1));
        for (j = 1; j <= k; j++) {
            q = min(j, pilesColSize[i - 1]);
            for (p = 0; p <= q; p++) {
                dp[j] = max(dp[j], tdp[j - p] + (p > 0 ? piles[i - 1][p - 1] : 0));
            }
        }
    }
    return dp[k];
}

解题思路：

宏定义：
- max(a, b)：返回 a 和 b 中的较大值。
- min(a, b)：返回 a 和 b 中的较小值。
动态规划数组初始化：
- dp[k + 1] 和 tdp[k + 1]：dp 数组用于存储当前状态下的最优解，tdp 数组作为临时数组，用于存储上一个状态的最优解，以便在更新 dp 时不会覆盖未使用的旧值。数组大小为 k + 1，因为可以选择的堆数从 0 到 k。
预处理每堆硬币的累积和：
- 遍历每一堆硬币 piles[i - 1]（注意数组索引从 0 开始，但堆的索引从 1 开始考虑，所以这里用 i - 1），将每堆硬币转化为累积和数组。即 piles[i - 1][j] 表示从第 1 堆到第 j 堆的累积硬币数量。这样做是为了方便后续直接通过索引获取任意连续堆的硬币总数。
动态规划状态转移：
- 外层循环遍历每一堆硬币。
- 使用 memcpy 复制 dp 数组到 tdp 数组，以保存上一个状态的最优解。
- 内层循环遍历所有可能的堆数 j（从 1 到 k）。
  - q = min(j, pilesColSize[i - 1])：确定在当前堆数限制下，最多可以选择多少堆。
  - 再内层循环遍历从 0 到 q 的所有可能选择堆数 p。
    - dp[j] = max(dp[j], tdp[j - p] + (p > 0 ? piles[i - 1][p - 1] : 0))：尝试更新状态。这里 tdp[j - p] 表示选择前 i-1 堆中 j-p 堆的最大硬币数，piles[i - 1][p - 1] 表示选择当前堆的前 p 堆的累积硬币数（注意这里因为累积和的原因，piles[i - 1][p - 1] 实际表示的是前 p 堆的总和，而非单独第 p 堆）。如果 p 为 0，即不选择当前堆的任何部分，则硬币数为 0。
返回结果：
- 最终返回 dp[k]，表示在不超过 k 堆的限制下，可以选择的最大硬币总数。