❀ 題目傳送門 ❀

https://atcoder.jp/contests/dp/tasks/dp_b

❀ 解題小技巧 ❀

就是上一題的進階版，其中 dp 為跳到第n個最省力之方法
因此只要想：現在這顆石頭花的力氣，就是上一顆石頭加上這兩顆的高度差。
而他可能從那些石頭跳過來呢？也就是n-1、n-2…n-K這幾顆。
需要最省力，所以用min()，每次都比較是否跳過來更省力，若是則替換當前dp[i]，否則維持原本。
解答要求跳到第 N 顆最省力，因此答案就是 dp[N]。

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

#define burst ios::sync_with_stdio(0); cin.tie(0);

int main(){
  burst
  int N, K;
  cin >> N >> K;
  int stone[100005], dp[100005];
  memset(dp, 0x3f, sizeof(dp));
  for(int i = 1; i <= N; i++){
    cin >> stone[i];
  }
  dp[1] = 0;
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= K && i - j > 0; j++){
      dp[i] = min(dp[i], dp[i - j] + abs(stone[i] - stone[i - j]));
    }
  }
  cout << dp[N];
  return 0;
}