Эффективный алгоритм C / C ++ в двумерном окне максимальной суммы

у меня есть c[N][M] матрица, где я применяю операцию с максимальной суммой над (K+1)² окно. Я пытаюсь уменьшить сложность наивного алгоритма.

В частности, вот мой фрагмент кода на C ++:

<!-- language: cpp -->

int N,M,K;
std::cin >> N >> M >> K;

std::pair< unsigned , unsigned > opt[N][M];
unsigned c[N][M];

// Read values for c[i][j]
// Initialize all opt[i][j] at (0,0).

for ( int i = 0; i < N; i ++ ) {
for ( int j = 0; j < M ; j ++ ) {

unsigned max = 0;
int posX = i, posY = j;

for ( int ii = i; (ii >= i - K) && (ii >= 0); ii -- ) {
for ( int jj  = j; (jj >= j - K) && (jj >= 0); jj -- ) {

// Ignore the (i,j) position
if (( ii == i ) && ( jj == j )) {
continue;
}

if ( opt[ii][jj].second > max ) {

max = opt[ii][jj].second;
posX = ii;
posY = jj;

}
}
}

opt[i][j].first  = opt[posX][posY].second;
opt[i][j].second = c[i][j] + opt[posX][posY].first;

}
}

Цель алгоритма — вычислить opt[N-1][M-1],

Пример: для N = 4, M = 4, K = 2 а также:

c[N][M] = 4 1 1 2
6 1 1 1
1 2 5 8
1 1 8 0

… результат должен быть opt[N-1][M-1] = {14, 11},

Однако сложность этого фрагмента О(N M K²). Моя цель состоит в том, чтобы уменьшить сложность времени выполнения. Я уже видел сообщения, как этот, но похоже, что мой «фильтр» не отделим, возможно, из-за операции суммирования.

Дополнительная информация (необязательный): по сути, это алгоритм, который разрабатывает оптимальную стратегию в «игре», где:

• Два игрока возглавляют одну команду в N × M темница.
• Каждая позиция подземелья имеет c[i][j] золотые монеты.
• Начальная позиция: (N-1,M-1) где c[N-1][M-1] = 0,
• Активный игрок выбирает следующую позицию для перемещения команды из позиции (x,y),
• Следующая позиция может быть любой из (x-i, y-j), i <= K, j <= K, i+j > 0, Другими словами, они могут двигаться только влево и / или вверх, до шага K по направлению.
• Игрок, который только что переместил команду, получает монеты в новой позиции.
• Активный игрок чередует каждый ход.
• Игра заканчивается, когда команда достигает (0,0),
• Оптимальная стратегия для обоих игроков: максимизируйте их собственную сумму золотых монет, если они знают, что противник следует той же стратегии.

Таким образом, opt[i][j].first представляет монеты игрока, который теперь будет двигаться от (i,j) в другую позицию. opt[i][j].second представляет монеты противника.