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 を使用しましたが、単純なパフォーマンス向上は、S からの戻り値を一時変数に配置し、>?: を使用して maxValue を設定することです。