Как уменьшить сложность?

Question

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

for(int i = 3; i < N; i++){ 
    for(int j= 3; j < T; j++){ 
    .. 

Я хочу уменьшить сложность. Как я могу это сделать?

Answer 1

Мне нужно понять, каков ваш базовый корпус рекурсии. Я думаю, что с этой информацией я мог бы превратить это в более эффективную конструкцию цикла. Но с тем, что я сейчас знаю, я бы просто транскрибировать первый функциональное определение в это логически C# эквивалент ...

int S(int i, int j) 
{ 
    if (?) // the base case, must be at least one, can have more then one. (e.g. when i=N or j=T) 
     return ?; // What gets returned ultimately controls how efficient we can make this. 

    var maxValue = S(i-1, j-1); 
    for (var k = j-2; k < i-3; k++) 
     maxValue = Math.Max(maxValue, S(k, j-3)); 
    return maxValue; 
} 

А внутри для цикла, мы можем сделать более эффективным, делая свои собственные сравнения вместо звоните в Math.Max. Я использовал Math.Max ​​просто, потому что его легче читать, но простое повышение производительности должно было бы вернуть возврат из S в временную переменную, а затем использовать> ?: для установки maxValue.