分治策略次序选择问题c语言实现

以下是分治策略次序选择问题的C语言实现：

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

#define MAX_N 100

// 分治策略次序选择问题
int minTime(int cost[][MAX_N], int n) {
    int dp[MAX_N][MAX_N] = {0}; // dp数组
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0; // 初始化dp数组
    }
    for (int len = 2; len <= n; len++) { // 枚举子问题规模
        for (int i = 1; i <= n - len + 1; i++) { // 枚举子问题起点
            int j = i + len - 1; // 子问题终点
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) { // 枚举分治点
                dp[i][j] = fmin(dp[i][j], dp[i][k] + dp[k+1][j] + cost[i][k] + cost[k+1][j]);
            }
        }
    }
    return dp[1][n]; // 返回最终答案
}

int main() {
    int n, cost[MAX_N][MAX_N];
    printf("请输入分治策略的数量n：");
    scanf("%d", &n);
    printf("请输入分治策略之间的时间复杂度：\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &cost[i][j]);
        }
    }
    printf("最小时间复杂度为：%d\n", minTime(cost, n));
    return 0;
}

输入格式为：

n
cost[1][1] cost[1][2] ... cost[1][n]
cost[2][1] cost[2][2] ... cost[2][n]
...
cost[n][1] cost[n][2] ... cost[n][n]

其中，n为分治策略的数量，cost[i][j]表示从第i个分治策略到第j个分治策略的时间复杂度。输出结果为最小时间复杂度。