2.徒步中的补给 #

问题描述 小 R 正在计划一次从地点 A 到地点 B 的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小 R 每天必须消耗 1 份食物。幸运的是，小 R 在路途中每天都会经过一个补给站，可以先购买完食物后再消耗今天的 1 份食物。然而，每个补给站的食物每份的价格可能不同，并且小 R 在购买完食物后最多只能同时携带 K 份食物。

现在，小 R 希望在保证每天食物消耗的前提下，以最小的花费完成这次徒步旅行。你能帮助小 R 计算出最低的花费是多少吗？

输入

n 总路程需要的天数 k 小 R 最多能同时携带食物的份数 data[i] 第 i 天补给站每份食物的价格

输出

• 返回完成这次徒步旅行的最小花费

约束条件

• 1 < n,k < 1000
• 1 < data[i] < 10000

测试样例 样例 1：

输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2] 输出：9

为了解决这个问题，我们需要确保小 R 在徒步旅行中每天都能消耗足够的食物，同时最小化总花费。我们可以通过动态规划的方法来解决这个问题，确保在每个补给站购买食物时考虑到当前和未来的价格以及携带量的限制。

方法思路 #

1. 动态规划定义：我们定义 dp[i][s] 为处理完前 i 天后剩余 s 份食物的最小花费。
2. 初始化：初始状态为 dp[0][0] = 0，表示在第 0 天结束时没有剩余食物且花费为 0。
3. 状态转移：对于每一天，我们遍历所有可能的剩余食物量 s，计算在该天购买不同数量的食物后转移到下一天的状态，并更新最小花费。
4. 购买限制：每天购买的食物的数量必须满足携带量的限制，并且确保购买后能够满足当天的消耗需求。

解决代码 #

function minCost(n, k, data) {
  const dp = new Array(n + 1).fill().map(() => new Array(k + 1).fill(Infinity))
  dp[0][0] = 0

  for (let i = 0; i < n; i++) {
    for (let s = 0; s <= k; s++) {
      if (dp[i][s] === Infinity) continue
      const price = data[i]
      const xMin = Math.max(0, 1 - s)
      const xMax = k - s
      for (let x = xMin; x <= xMax; x++) {
        const newS = s + x - 1
        if (newS < 0 || newS > k) continue
        dp[i + 1][newS] = Math.min(dp[i + 1][newS], dp[i][s] + x * price)
      }
    }
  }

  return dp[n][0]
}

// 测试样例
console.log(minCost(5, 2, [1, 2, 3, 3, 2])) // 输出9

代码解释 #

1. 初始化动态规划数组：dp 数组初始化为一个二维数组，每个元素初始化为无穷大，表示不可达状态。dp[0][0] 初始化为 0，表示初始状态。
2. 遍历每一天：对于每一天 i，遍历所有可能的剩余食物量 s。
3. 计算购买范围：确定当天可以购买的食物数量的最小值和最大值，确保购买后不会超过携带限制并能满足当天消耗。
4. 状态转移：对于每个可能的购买数量 x，计算新的剩余食物量 newS，并更新 dp[i + 1][newS] 的最小花费。
5. 返回结果：最后返回处理完所有天数后的最小花费，即 dp[n][0]，表示在最后一天结束时没有剩余食物的最小花费。

这种方法通过动态规划有效考虑了每一天的不同状态，确保在满足每天消耗需求的前提下，最小化总花费。