Javaデータ構造とアルゴリズムの動的計画

シーケンス
「Dynamic Programming」の「Programming」はプログラミングの意味ではなく、DPがステップごとに得たサブ問題の結果をテーブルに格納し、サブ問題に遭遇するたびにもう一度解く必要はなく、テーブルを問い合わせるだけでよいテーブル処理法を指す.
一、概念
動的計画アルゴリズムは、問題を分割し、問題の状態と状態の関係を定義します.動的計画アルゴリズムの基本思想は分治法と類似しており,解くべき問題をいくつかのサブ問題に分解する(フェーズ)、サブフェーズを順番に解き、前のサブ問題の解は、後のサブ問題の解に有用な情報を提供する.いずれかのサブ問題を解く場合、様々な可能なローカル解をリストし、最適に達する可能性のあるローカル解を決定することによって保持し、他のローカル解を捨てる.各サブ問題を順番に解決し、最後のサブ問題は初期問題の解である.
欲張りアルゴリズム:前回のデータ構造とアルゴリズムの欲張りブログ
二、思想
動的計画には、次の2つの性質があります.

オーバーラップサブ問題

最適サブ構造

欲張りアルゴリズム:

貪欲選択性質

最適サブ構造

最適サブ構造特性とは,問題の最適解がそのサブ問題の最適解を含む場合,その問題が最適サブ構造特性を有すると称し,オーバーラップサブ問題はサブ問題が複数回用いられる可能性があることを指し,複数回計算し,動的計画はそのオーバーラップサブ問題を解消するために設計された.実は貪欲なアルゴリズムは1種の特殊な動態計画で、それは貪欲な選択の性質を持っているため、サブ問題が1回しか計算されないことを保証して、何度も計算されないので、貪欲なアルゴリズムは実は最も簡単な動態計画です.
動的計画は大きく4つのステップに分けられます.

最適解の構造特徴(オーバーラップサブ問題を備えているかどうか、最適サブ構造特徴、必ずdp配列の意味を理解しなければならない)

を分析する.

最適値再帰式を確立する(状態遷移方程式を探し、履歴を利用して現在を更新する)

最適値(境界値を定義)

を下から上へ計算する.

構造最適解(戻り最適解)

三、応用例
1、Climbing Stairs
質問:カエルは階段を跳んで、一回に1歩あるいは2歩跳ぶことしかできなくて、どれだけの方法がN階段まで跳ぶことがあります
分析:

dp[n]は第N-1ステップの最適解

を表す.

状態遷移dp[n]=dp[n-1]+dp[n-2]

境界dp[0]=1,dp[1]=2

はdp[n-1]

を返す.

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

2、Unique Paths
質問:ロボットが歩く、左上から右か下しか歩けない、右下まで歩く、全部でいくつかの歩き方
分析:

dp[i][j]は左上角が右下角に進む最適解

を表す.

状態遷移dp[i][j]=dp[i-1][j]+dp[i][j-1]

境界dp[0][i]=1,dp[1][0]=1

はdp[m-1][n-1]

を返す

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1]; 
    }
}

3、Edit Distance
質問:2つの文字列の編集例では、文字列を挿入、削除、置換できます.
分析:

dp[i][j]文字列長iから文字列長jへの編集例

状態遷移dp[i][j]=Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + temp);i=jの場合temp=0、不等の場合temp=1

境界dp[0][i]=i dp[i][0]=i

はdp[m][n]

を返す

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                int temp = 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    temp = 0;
                }
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + temp);
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

4、Longest Common Subsequence
質問:最長男共通シーケンス、2つのサブシーケンスが連続しないs 1=「abcde」s 2=「ace」共通はs=「ace」
分析:

dp[i][j]は、文字列長iから文字列長jまでの共通サブシーケンス

を表す.

状態遷移i=j時dp[i][j]=dp[i-1][j-1]+1不等時dp[i][j]=Math.max(dp[i - 1][j], dp[i][j - 1])   

境界dp[0][i]=0 dp[i][0]=0

はdp[m][n]

を返す

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 0; i <= text1.length(); i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= text2.length(); i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

5、Maximum Length of Repeated Subarray
 
問題:最長子列、2つのサブ列は連続arrでなければならない[1]={1,2,3,2,1}arr 2={3,2,1,4,7}共通はsub={3,2,1}
分析:

dp[i][j]は、文字列長iから文字列長jまでの共通サブシーケンス

を表す.

状態遷移i=jのときdp[i][j]=dp[i-1][j-1]+1

境界dp[0][i]=0 dp[i][0]=0

はres=Mathを返す.max(res,dp[m][n])

class Solution {
    public int findLength(int[] A, int[] B) {
        int[][] dp=new int[A.length+1][B.length+1];
        for (int i=0;i<=A.length;i++){
            dp[i][0]=0;
        }
        for (int j=0;j<=B.length;j++){
            dp[0][j]=0;
        }
        int res=0;
        for (int m=1;m<=A.length;m++){
            for (int n=1;n<=B.length;n++){
                if (A[m-1]==B[n-1]){
                    dp[m][n]=dp[m-1][n-1]+1;
                    res=Math.max(res,dp[m][n]);
                }
            }
        }
        return res;
    }
}

まだたくさんの経典の例があって、絶えず更新しています