Минимальная сумма из n чисел с k пробелами между заданным массивом размера N

Question

Используя динамическое программирование, я должен найти эффективный алгоритм для решения следующей задачи:

В качестве входных данных мы получаем массив случайных чисел размером N, int k, который является минимальным расстоянием междувыбранные числа и int n, то есть общее количество чисел, которые мы должны выбрать.Цель задачи - выяснить, какова минимально возможная сумма n выбранных чисел.Я не могу понять, как подойти к этой проблеме.

Например, если у нас есть следующий массив:

arr = [5, 5, 3, 3, 2, 2, 3, 3, 5, 5, 5, 5, 5, 3, 2, 5]
N = 16
k = 4
n = 3

, результат будет 8 (3+3+2), выбрав числа вуказатель 2, 7 и 14.

Answer 1

Я кодировал решение на с ++, код по большей части читабелен, но если у вас есть некоторая двусмысленность в его понимании, прокомментируйте ниже.

#include<iostream>
#include<vector>
using namespace std;
int number_of_elements_to_be_picked, number_of_elements, k;
int main(){
      cin >> number_of_elements >> k >> number_of_elements_to_be_picked;
      vector<int> a(number_of_elements);
      vector<vector<int> > store(number_of_elements, vector<int> (number_of_elements_to_be_picked+1));
      for(int i = 0; i < number_of_elements; i++){
              cin >> a[i];
              store[i][1] = a[i];
      }
      for(int i = 0; i < number_of_elements; i++){
              for(int j = 2; j <= number_of_elements_to_be_picked; j++){
                      if(i == k*(j-1))
                              store[i][j] = store[i-k][j-1]+a[i];
                      else if(i > k*(j-1))
                              store[i][j] = min(store[i-k][j-1]+a[i], store[i-1][j]);
              }
      }
      cout << store[number_of_elements-1][number_of_elements_to_be_picked] << "\n";
      return 0;
}

edit: у меня были неверно названные переменные, авторская запись: -
N = число_элементов, n = число_элементов_в_базе, k = k