for-loop - 如何降低复杂度？

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 simple 是因为它更易于阅读，但一个简单的性能增强是将 S 的返回值放入一个临时变量中，然后使用 >?: 设置 maxValue。