如何降低复杂度？

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; 
} 

而且里面的for循环中，我们可以使事情更加有效的做自己的比较，而不是调用Math.Max。我使用Math.Max很简单，因为它更易于阅读，但简单的性能增强将是将S的返回放置到一个临时变量中，然后使用>？：设置maxValue。