常用アルゴリズム整理:ダイナミックプランニング

動的計画とは
動的計画は、 と呼ぶことができず、 と呼ぶべきか、 と呼ぶべきか. とは異なり、二分検索はコードで表すことができ、すべての問題を解決する考え方はほとんど同じです.動的計画は実際にはコードで表すことができず、それぞれの問題の解決方法はコードで書くことができるかもしれないので、動的計画の定義だけを見ると理解しにくいので、複数の問題を連絡してこそ本当に理解することができます.
ダイナミックプランニングの特徴は、大きな問題をいくつかの小さな問題に分解することであり、これらの小さな問題の間で、すべての小さな問題は前の小さな問題から計算することができます.通常、これらの小さな問題は実際には具体的な状態です.問題がダイナミック・プランニングで解決できる場合は、次のような特徴を満たす必要があります.

この問題はdp[0], dp[1], … , dp[n]の状態に分解することができ、最終的な答えはそのうちの1つの状態であり、一般的にdp[n]である.(またはdp[n][m]などより多くの次元で、ここでは1次元だけを持っています)

のうち、dp[i]は、dp[0] ~ dp[i-1]または`dp[i+1]~dp[n]によって算出することができる.

定義だけを見ていると、DPは必ず分治法で解決できることがわかります.ではなぜDPアルゴリズムで解決する必要があるのかというと,分治法アルゴリズムは大量の繰返し計算を行うことが多く,動的計画は状態を記録することで時間の複雑さが大幅に低下するからである.多くの場合、時間の複雑さはO(2^n)からO(n^2)に低減することができる.計算されたノードをキャッシュするために分割法にCacheを加えると、彼の時間の複雑さはDPと同じであり、実際にはDP = DC + Cacheである.
上記の2つの特徴から分かるように、DP問題の難点は2つあります.

dp[i]、すなわち問題をどのように分割するかを定義する場合、ステータス

を定義する.

は、dp[i]をどのように計算するか、すなわち、前の状態から次の状態

をどのように計算するかである.
この2つの難点に加えて,初期値と可能な境界オーバーフローの問題を処理することもある.
また,問題がすべての解を要求する場合,DPは用いないに違いない.DPは一般に最適解または解法数を求める.
シンプルなダイナミックプランニング
最も簡単な動的計画です.この問題を参照してください.https://leetcode.com/problems/triangle/
ここでは,問題で与えられたtriangleと同様の配列dpを用いて状態を格納する.上記の2つの難点を解決します.

問題を分割したら?実はここでdp[i][j]はtriangle[i][j]という点にジャンプするために必要な最短経路を表しています.

dp[i][j]を計算すると?dp[i][j]は実は彼の上層の近接ノードの中の比較的小さいdp[i][j] = Math.min(last[j-1], last[j])+t[j]

を取っている.
それから境界条件を処理すれば、この問題は解決できます.コードは次のとおりです.

var minimumTotal = function(triangle) {
    if(!triangle.length) return 0;
    var dp = [triangle[0]];
         //          

    for(var i=1;i<triangle.length;i++) {
        var last = dp[i-1];
        var row = [];
        var t = triangle[i];
        for(var j=0;j<t.length;j++) {
            if(j === 0) row.push(last[0]+t[0]);
                 //     
            else if(j === t.length-1) row.push(last[last.length-1]+t[t.length-1]);
                 //     
            else row.push(Math.min(last[j-1], last[j])+t[j]);
        }
        dp.push(row);
    }

    var r = dp.pop(), min = r[0];
    for(i=0;i<r.length;i++) {
        if(r[i]<min) min = r[i];
    }
    return min;
};

時間の複雑さを分析してみると、nで層数を表すと、ノード数は約O(n^2)であり、このアルゴリズムでは実際に三角全体を1回遍歴しただけなので、時間の複雑さもO(n^2)である.
DCと比較すると、ここではDCのアルゴリズムを簡単に書くことができ、DPよりも簡単です.DCアルゴリズムは,1つのノードi,jの値を計算するたびに,i-1,j-1とi-1,jをそれぞれ計算する2つの再帰を行う必要があるため,呼び出すたびに2つの新しい再帰を生成し,各層の計算量はいずれも上位層の2倍であり,時間的複雑度はO(2^n)である.
簡単な問題をもう一つ見てみましょう.https://leetcode.com/problems/unique-paths/
ここでは、i,jに移動したすべての異なる経路の個数をdp[i][j]で表す.コードは次のとおりです.

var uniquePaths = function(m, n) {
    var dp = [], i, j;
    for(i=0;i<m;i++) {
        var row = [];
        for(j=0;j<n;j++) {
            row.push(0);
        }
        row[0] = 1;
        dp.push(row);
    }

    for(i=0;i<m;i++) {
        for(j=1;j<n;j++) {
            if(i === 0) dp[i][j] = dp[i][j-1];
            else dp[i][j] = dp[i][j-1] + dp[i-1][j];
        }
    }

    return dp[m-1][n-1];
};

中難易度の問題
上記の2つのDP問題はいずれもEasyの難易度の問題であり、Easyは主に私たちが定義した2つの難点に対して実際には簡単に解決できると言っている.すなわち、dp[i]の定義が容易であり、dp[i]の計算も容易である.次のいくつかの問題は少し難しいです.
最初の問題は、https://leetcode.com/problems/longest-increasing-subsequence/
ここで、dp[i]をどのように定義するかは、主に2つの考えがあるかもしれません.

0~i個の元素の最長子配列

i要素で終わる最長子シーケンス

第1の定義を用いると、dp[0] ~ dp[i-1]によってdp[i]を計算することはできないことが分かった.なぜなら、前の長男シーケンスの末尾値がi要素より小さいかどうかは分からないからである.2番目の定義しか選択できません
すなわちdp[i] i であり、これによりdp[i]を計算することができ、dp[0~i-1]を繰り返して、現在の要素よりも小さく最も長いサブシーケンスを見つけ、その後、長さに自分を加えるとdp[i]であり、具体的な解法は以下の通りである.

var lengthOfLIS = function(nums) {
    if(nums.length <= 1) return nums.length;

    var dp = [], i, result=1;

    for(i=0;i<nums.length;i++) {
        dp.push(1);
    }

    for(i=1;i<nums.length;i++) {
        for(var j=0;j<i;j++) {
            if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], 1+dp[j]);
        }
        result = Math.max(dp[i], result);
    }
    return result;
};

このやり方の時間的複雑さはO(n^2)であり,彼は二重ループであるからである.
2番目の問題は、https://leetcode.com/problems/palindrome-partitioning-ii/
この問題はかなり難しいですが、ここではdp[i]を前のi要素に必要な最小cutと定義します. i 、すなわち、現在のi番目の要素は含まれないことに留意されたい. i ではなく0~i を定義する理由については、主に境界条件を処理するのが便利であるため、0~i と定義しても解くことができる.dp[i]を定義したら、その値を計算する方法が必要です.明らかな構想の一つは、dp[j=0~i-1]を遍歴し、j~i要素が回文文字列であれば、dp[i]=dp[j]+1は、最小値を1つ取ればよいということである.
そうすると、このようなコードが表示されます.

for(i=1;i<=s.length;i++) {
    for(var j=0;j<i;j++) {
        if(isPalindrome(j,i-1)) dp[i] = Math.min(dp[j]+1, dp[i]);
    }
}

ここにはもう2つのサイクルがあります.つまり、時間の複雑さは少なくともO(n^2)なので、その中のisPalindrome関数は再びサイクルすることはできません.そうしないとO(n^3)になります.そうしないと、タイムアウトになります.すべての状況を事前に計算し、isPalindrome[n][n]の配列に保存する方法があります.これにより、O(n^2)の余分なスペースが必要になります.実際にleetcodeでそうすると、メモリオーバーエラーが報告されます.
このような考え方では,O(n^2)の時間的複雑さを得ることができず,同時に空間的複雑さはO(n)の解法であることが明らかになった.この考え方は比較的容易に考えられ、実現は複雑ではない.Javaで通れるようですが、JSでは通れません.このアイデアの完全なコードを貼ってください.

var minCut = function(s) {
    if(s.length <= 1) return 0;
    var isPalindrome = caculatePalindrome(s);
    var dp = [-1];

    for(var i=1;i<=s.length;i++) {
    dp.push(i-1);
    }

    for(i=1;i<=s.length;i++) {
        for(var j=0;j<i;j++) {
            if(isPalindrome[j][i-1]) dp[i] = Math.min(dp[j]+1, dp[i]);
        }
    }

    return dp[s.length];
};

var caculatePalindrome = function(s) {
    var dp = [];

    for(var i=0;i<s.length;i++) {
        var row = [];
        for(var j=0;j<=i;j++) {
            row.push(false);
        }
        dp.push(row);
    }

    for(i=0;i<s.length;i++) {
        for(j=0;j<=i;j++) {
            if(i === j) dp[j][i] = true;
            else if(j === i-1) dp[j][i] = (s[i] === s[j]);
            else dp[j][i] = (s[i] === s[j] && dp[j+1][i-1]);
        }
    }

    return dp;
}

ここで私たちは考えを変えて、この考えはとても考えにくいです.つまり,実際には2層目のループと同時に,返信文字列であるか否かを判断することができ,追加の判断は必要ない.具体的には、コードを直接見て説明します.

var minCut = function(s) {
    if(s.length <= 1) return 0;
    var dp = [];

    for(var i=0;i<=s.length;i++) {
        dp.push(i-1);
    }

    for(i=0;i<=s.length;i++) {
        for(var j=0;i-j>=0 && i+j<s.length && s[i-j] === s[i+j]; j++) {
            dp[i+j+1] = Math.min(dp[i+j+1], dp[i-j]+1);
        }
        for(j=0;i-j+1>=0 && i+j<s.length && s[i-j+1] === s[i+j]; j++) {
            dp[i+j+1] = Math.min(dp[i+j+1], dp[i-j+1]+1);
        }
    }
    return dp[s.length];
}

この解法は最高票のその答えを参考にしたものです.第2層ループの場合、dp[i+1]を計算すると、返信文字列かどうかを直接判断することはできないに違いないので、この方法はdp[i+1]ではなくdp[i+j+1]を計算する巧みな設計をした.これにより、jが徐々に増加すると、i-j ~ i+jが返信文字列であるか否かを判断することができる.
この解法の時間的複雑さはO(n^2)であることが容易にわかる.
3番目の問題は、https://leetcode.com/problems/word-break/
この問題は比較的簡単で、やはり前の問題の構想と似ていて、dp[i]で前のi要素が単語に切断できるかどうかを表しています.そして、ここで前の問題より簡単なところは、前の問題の回文文字列が判断しにくいことです.ここでは辞書で簡単に判断できるのではないでしょうか.具体的な解法は以下の通りです.

var wordBreak = function(s, wordDict) {
    var maxWordLength = 0;
    wordDict.forEach(function(w){
        maxWordLength = Math.max(w.length, maxWordLength);
    });

    var dp = [true];

    for(var i=1;i<=s.length;i++) dp.push(false);

    for(i=1;i<=s.length;i++) {
        for(var j=1;j<=maxWordLength && j<=i;j++) {
            if(wordDict.has(s.slice(i-j,i)) && dp[i-j]) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length];
};

一つ注意したいのは、2層目のループの場合、jの最大値はiではなくmaxWordLengthなので、時間の複雑さはO(NL)でO(n^2)であり、そのうちLはmaxWordLengthである.
まず、上記の比較的簡単な動的計画問題を紹介します.回文文字列が難しい以外は、EasyまたはMediumレベルで、bug freeを行う必要がある問題に属しています.
次はもっと複雑な動的計画問題を続けます.これらの問題の特徴は2つのシーケンス間のいくつかの操作を試験することです.
デュアルシーケンス:leetcodeにLongest Common Subsequenceがありませんhttps://leetcode.com/problems/edit-distance/ https://leetcode.com/problems/distinct-subsequences/ https://leetcode.com/problems/interleaving-string/