编辑代码

#include <stdio.h>

// 定义最大景点数量和最大花费天数
#define MAX_N 4
#define MAX_DAYS 4
// 函数声明
int maxScore(int times[], int scores[], int n);

int main() {
    // 景点信息
    int times[MAX_N] = {1, 2, 3, 1};
    int scores[MAX_N] = {7, 8, 9, 6};
    int n = sizeof(times) / sizeof(times[0]);
    // 调用最大评分函数
    int result = maxScore(times, scores, n);
    // 输出结果
    printf("最大评分为: %d\n", result);
    return 0;
}

// 最大评分函数
int maxScore(int times[], int scores[], int n) {
    // 初始化二维数组 dp
    int dp[MAX_N + 1][MAX_DAYS + 1];

    // 初始化第一行和第一列为0，表示没有景点或者花费天数为0
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= MAX_DAYS; j++) {
        dp[0][j] = 0;
    }
    // 动态规划过程
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= MAX_DAYS; j++) {
            if (j < times[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - times[i - 1]] + scores[i - 1]) ?
                           dp[i - 1][j] : dp[i - 1][j - times[i - 1]] + scores[i - 1];
            }
        }
    }
    // 返回最大评分
    return dp[n][MAX_DAYS];
}