C语言运用备忘录法解决钢条切割问题

钢条切割问题是一个经典的优化问题，它的基本思想是将一根长度为 n 的钢条切割成若干段长度不同的小钢条，使得这些小钢条的长度之和最大。

备忘录法（Memoization）是一种自顶向下的动态规划方法，它的基本思想是将计算过的子问题的结果记录下来，避免重复计算。

下面是使用备忘录法解决钢条切割问题的示例代码（假设小钢条的价格存储在数组 price 中，其中 price[i] 表示长度为 i 的小钢条的价格）：

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

#define MAX_N 1000

int price[MAX_N + 1];
int memo[MAX_N + 1];

int max(int a, int b) {
    return a > b ? a : b;
}

int cut_rod(int n) {
    if (n == 0) {
        return 0;
    }
    if (memo[n] > 0) {
        return memo[n];
    }
    int q = -1;
    for (int i = 1; i <= n; i++) {
        q = max(q, price[i] + cut_rod(n - i));
    }
    memo[n] = q;
    return q;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &price[i]);
    }
    printf("%d\n", cut_rod(n));
    return 0;
}

在上面的代码中，cut_rod(n) 函数是计算长度为 n 的钢条的最大价值的函数。如果 memo[n] 大于 0，说明之前已经计算过长度为 n 的钢条的最大价值，直接返回 memo[n] 的值即可。否则，依次枚举钢条的长度，计算出最大价值，并将结果存储在 memo[n] 中，避免重复计算。

该算法的时间复杂度为 O(n^2)，空间复杂度也为 O(n^2)，其中 n 为钢条的长度。