时间轴

2025-10-10

init

题目：

P3147 从魔法师身上吸取的最大能量

https://leetcode.cn/problems/taking-maximum-energy-from-the-mystic-dungeon/?envType=daily-question&envId=2025-10-10

从后向前遍历

假设需要从 0..k-1 开始，一共有路径{0..k-1} - {n-1-k..n-1}
每条路径起点为 0~k-1，计算每条路径的从某一起点开始的最大能量，然后从这几个路径的最大能量中找最大的。
对于一条路径的最大能量就是找从一个起点开始到最后一个值的最大和，那么不妨从最后一个起点向前遍历，记录最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <climits>
#include <vector>
using std::vector;

class Solution {
public:
  int maximumEnergy(vector<int> &energy, int k) {

    int i, j;
    int total = 0;
    int n = energy.size();
    vector<int> way(n, INT_MIN);

    for (i = 0; i < k; i++) { // 每条路径
      j = 0;
      while (i + j * k < n) {
        j++;
      }
      j--;
      total = 0;

      while (j >= 0) {
        total += energy[i + j * k];
        way[i] = std::max(way[i], total);
        j--;
      }
    }

    return *std::max_element(way.begin(), way.end());
  }
};

#include <stdio.h>
int main() {
  Solution s;
  vector<int> vec = {5, 2, -10, -5, 1};
  printf("%d\n", s.maximumEnergy(vec, 3));
}

动态规划

因为最大能量和以前的状态有关，所以也可以用动态规划来解决：
假设 dp[i]为到达第 i 个魔法师所获得的最大能量,那么

边界条件：

由于最终到到达没有魔法师的区域，那么必须要到达最后 k 的魔法师。因此最终最大值从最后 k 个 dp 里找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <algorithm>
#include <vector>
using std::vector;

class Solution {
public:
  int maximumEnergy(vector<int> &energy, int k){

    int n = energy.size();
    int res;
    vector<int> dp(n);

    std::copy(energy.begin(), energy.end(), dp.begin());

    for (int i = k; i < n; i++) {
      dp[i] = std::max(energy[i], dp[i - k] + energy[i]);
    }

    res = *std::max_element(dp.end() - k, dp.end());

    return res;
  }
};