C语言/数据结构算法训练:动态规划求解徒步旅行最小食物花费（背包容量限制+每日消耗）

问题描述小R正在计划一次从地点A到地点B的徒步旅行总路程需要N天。为了在旅途中保持充足的能量小R每天必须消耗1份食物。幸运的是小R在路途中每天都会经过一个补给站可以购买食物进行补充。每个补给站的食物每份的价格可能不同并且小R最多只能同时携带K份食物。小R在开始旅行前没有携带任何食物。他需要在每天的补给站购买若干份食物可以是0份但必须保证购买后不会超过携带容量K并且要确保当天及之后不会断粮然后消耗1份食物消耗发生在购买之后。小R希望以最小的总花费完成旅行。请帮助小R计算出最低的花费是多少。输入格式输入包含三个参数n: 一个整数表示总天数k: 一个整数表示小R最多能同时携带的食物份数data: 一个整数列表长度为n表示每天补给站的食物价格输出格式返回一个整数表示最小总花费。约束条件1 n 100001 k 1001 data[i] 1000代码#include stdio.h#include limits.h // 必须添加此头文件否则 INT_MAX 未定义int minCost(int n, int k, int* data, int dataSize) {int dp[100][100];for (int i 0; i n; i) {for (int j 0; j k; j) {dp[i][j] INT_MAX / 2;}}dp[0][0] 0;for (int i 0; i n; i) {for (int j 0; j k; j) {if (dp[i][j] INT_MAX / 2) continue;for (int x 0; x k - j; x) {if (j x 1) {int newCarry j x - 1;int newCost dp[i][j] x * data[i];if (newCost dp[i 1][newCarry]) {dp[i 1][newCarry] newCost;}}}}}int result INT_MAX;for (int j 0; j k; j) {if (dp[n][j] result) {result dp[n][j];}}return result;}int main() {int data[] {1, 2, 3, 3, 2};printf(%d\n, minCost(5, 2, data, 5));return 0;}运行结果