Java版高度なデータ構造アルゴリズム-動的計画アルゴリズム(一般的な筆記試験の面接問題を解決する)

知識の学習は点滴記録にあり、たゆまぬ努力を続けている.知識の学習には深さと広さが必要で、表面だけに流れてはいけない.知識は総括するのが上手で、理解できるだけではなくて、更にどのように表現することを知っています!
文書ディレクトリ

動的計画アルゴリズム思想

動的計画基本ステップ

硬貨問題

最大フィールドおよび問題

LIS最長非降下子シーケンス問題

を求める

LCS最長共通サブシーケンス問題

を求める

0-1リュックサック問題

デジタル三角形問題

ダイナミックプランニングアルゴリズム思想
動的計画アルゴリズムは、通常、ある最適な性質を有する問題を解くために使用される.このような問題では,実行可能な解が多数存在する可能性があり,各解は1つの値に対応し,最適値を持つ解を見つけたい.
動的計画アルゴリズムは分治法と類似しており,その基本思想も解くべき問題をいくつかのサブ問題に分解し,まずサブ問題を解き,その後これらのサブ問題の解から原問題の解を得る.
しかし、分治法とは異なり、動的計画アルゴリズムの解に適用される問題であり、分解されたサブ問題は互いに独立していないことが多い.すなわち、次のサブ段階の解は前のサブ段階の解に基づいてさらに解を求め、このような問題が分治法で解を求めると、何度も計算され、効率が低いサブ問題がある.
解決したサブ問題の結果を保存し、必要に応じてサブ問題の答えを見つけることができれば、大量の計算を繰り返すことを避けることができ、サブセットツリーで同じ問題(例えば0-1リュック)を解決するのにかかる指数時間よりも多項式の時間アルゴリズムを得ることができます.
しかしこれは,動的プランニングが必ずしもサブセットツリーよりも問題を解決する効率が高いというわけではなく,サブセットツリーが問題を解決する時間的複雑さは指数レベルのO(2 n)O(2^n)O(2 n)であるが,適切な剪断操作を加えることで,サブセットツリーの遍歴効率を大幅に向上させることができる.
私たちは1つの表ですべての解けたサブ問題の答えを記録することができて、このサブ問題が後で使われるかどうかにかかわらず、それが計算された限り、その計算結果を表に記入することができます.これは動的計画アルゴリズムの基本的な考え方で、具体的な問題は動的計画アルゴリズムの形式を採用するのは多種多様ですが、それらはすべて同じ記入フォーマットを持っています.
動的計画の基本手順
1.問題の最適解の性質を探し出し、その構造特徴を描写する(状態を探す).再帰的定義最適値(状態遷移方程式を探す).問題の最適値4を下から上へ算出する.最適値算出時に得られた情報に基づいて最適解を構築する
核心は問題の「状態」と「状態遷移方程式」を見つけることである.
コイン問題
質問説明:1,3,5分の硬貨があり、指定された価値に達するには、少なくともいくつの硬貨が必要ですか?状態dp(i)はiの価値に必要な最小の硬貨の数を表します.状態変換方程式:dp(i)=min{dp(i-vj)+1}で、i>=vj、iは価値を表し、vjはj番目の硬貨の価値を表し、コードは以下の通りです.

public static void main(String[] args) {
    /**
     * dp(i)：  i            
     * dp(i) = min{dp(i-vj) + 1};   i-vj>=0，vj   j      
     */
    int[] ar = {1,3,5};
    int val = 11;
    int[] dp = new int[val+1];

    for (int i = 1; i <= val; i++) {
        dp[i] = i; //        ，         1   ，      
        for (int j = 0; j < ar.length; j++) {
            if(i >= ar[j] && (dp[i-ar[j]] + 1) < dp[i]){
                dp[i] = dp[i-ar[j]] + 1;
            }
        }
    }

    System.out.println(Arrays.toString(dp));
    System.out.println(dp[val]);
}

最大フィールドと問題
質問説明:n個の整数が与えられ、負数からなる可能性のあるシーケンスa[1],a[2],...,a[n]が与えられ、このシーケンス、例えばa[i]+a[i+1]+...+a[j]のフィールド和の最大値が求められ、与えられた整数がいずれも負数である場合、フィールド和を0と定義する.この問題は動的計画アルゴリズムで解き、状態dp[i]はi番目の要素で終わる最大フィールド和を表し、状態変換方程式は:d[i]=max{a[i],dである[i-1]+a[i]}コードは次のとおりです.

public class DPMaxChildSegmentSum {
    public static void main(String[] args) {
        int[] ar = {12,-16,8,-5,9,-12,10} ;
        int[] dp = new int[ar.length];
        int sum = maxSegmentSum(ar, dp);
        System.out.println(Arrays.toString(dp));
        System.out.println(sum);
    }

    private static int maxSegmentSum(int[] ar, int[] dp) {
        dp[0] = ar[0] >= 0? ar[0] : 0;
        int maxSum = dp[0];

        for(int i=1; i<ar.length; ++i){
            dp[i] = dp[i-1] + ar[i];
            if(dp[i] < 0){
                dp[i] = 0;
            }

            if(maxSum < dp[i]){
                maxSum = dp[i];
            }
        }

        return maxSum;
    }
}

LISの最も長い非降下子のシーケンスの問題を求めます
この問題は動的計画アルゴリズムを用いて解決され,その状態dp[i]はi番目の要素で終わる最長非降下子シーケンスの長さ値を表し,状態遷移方程式はdp(i)=max{1,dp(j)+1}のjであり,コードは以下の通りである.

public class DPLISLength {
    public static void main(String[] args) {
        String str = "asdfiez";
        int[] dp = new int[str.length()];
        int length = LIS(str, str.length(), dp);
        System.out.println("LISLength:" + length);
    }

    private static int LIS(String str, int length, int[] dp) {
        int maxlen = 0;

        for (int i = 0; i < length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(str.charAt(j) < str.charAt(i)
                        && dp[j]+1 > dp[i]){
                    dp[i] = dp[j] + 1;
                }
            }

            if(maxlen < dp[i]){
                maxlen = dp[i];
            }
        }

        return maxlen;
    }
}

LCSの最も長い共通のサブシーケンスの問題を求めます

/**
 *    :                
 *       
 *  Xn = {X1, X2, X3, ... , Xn}
 *  Yn = {Y1, Y2, Y3, ... , Yn}
 * 
 *                 
 *  1.  Xn == Yn，  
 *  LCS = LCS{[X1...Xn-1], [Y1...Yn-1]} + Xn
 * 
 *  2.  Xn != Yn，  
 *  LCS = LCS{[X1...Xn], [Y1...Yn-1]}
 *  LCS = LCS{[X1...Xn-1], [Y1...Yn]}
 * @param args
 */
public static void main(String[] args) {
    String str1 = "abcsafsa";
    String str2 = "cafa";
    int length = LCS(str1, str2, str1.length(), str2.length());
    System.out.println("length1:" + length);
}

/**
 *      LCS  
 * @param str1
 * @param str2
 * @param i
 * @param j
 * @return
 */
private static int LCS(String str1, String str2, int i, int j) {
    int maxlen = 0;
    //                ，       ，      ，      
    int[][] dp = new int[i+1][j+1];
    for(int m=1; m <= i; ++m){
        for(int n=1; n <= j; ++n){
            if(str1.charAt(m-1) == str2.charAt(n-1)){
                dp[m][n] = dp[m-1][n-1] + 1;
            } else {
                dp[m][n] = Math.max(dp[m-1][n], dp[m][n-1]);
            }

            if(maxlen < dp[m][n]){
                maxlen = dp[m][n];
            }
        }
    }
    return maxlen;
}

上のコードは最長共通サブシーケンスの長さを印刷するだけで、最長共通サブシーケンスの要素を印刷したい場合は、dpテーブルの方向を記録し、遡及法で要素印刷を行います.コードは以下の通りです.

/**
 *    :                
 *       
 *  Xn = {X1, X2, X3, ... , Xn}
 *  Yn = {Y1, Y2, Y3, ... , Yn}
 *
 *                 
 *  1.  Xn == Yn，  
 *  LCS = LCS{[X1...Xn-1], [Y1...Yn-1]} + Xn
 *
 *  2.  Xn != Yn，  
 *  LCS = LCS{[X1...Xn], [Y1...Yn-1]}
 *  LCS = LCS{[X1...Xn-1], [Y1...Yn]}
 * @param args
 */
public static void main(String[] args) {
    String str1 = "abcsafsa";
    String str2 = "cafa";
    //     ，  LCS     
    int[][] arr = new int[str1.length()+1][str2.length()+1];
    int length = LCS(str1, str2, str1.length(), str2.length(), arr);
    System.out.println("length1:" + length);

    backstrace(str1, str1.length(), str2.length(), arr);
}

/**
 *      LCS  
 * @param str1
 * @param str2
 * @param i
 * @param j
 * @param arr
 * @return
 */
private static int LCS(String str1, String str2, int i, int j, int[][] arr) {
    int maxlen = 0;
    //                ，       ，      ，      
    int[][] dp = new int[i+1][j+1];
    for(int m=1; m <= i; ++m){
        for(int n=1; n <= j; ++n){
            if(str1.charAt(m-1) == str2.charAt(n-1)){
                dp[m][n] = dp[m-1][n-1] + 1;
                arr[m][n] = 1;
            } else {
                if(dp[m-1][n] > dp[m][n-1]){
                    dp[m][n] = dp[m-1][n];
                    arr[m][n] = 2;
                } else {
                    dp[m][n] = dp[m][n-1];
        		    arr[m][n] = 3;
                }
            }

            if(maxlen < dp[m][n]){
                maxlen = dp[m][n];
            }
        }
    }
    return maxlen;
}

/**
 *     LCS     
 * @param str1
 * @param length
 * @param length1
 * @param arr
 */
private static void backstrace(String str1, int length,
                               int length1, int[][] arr) {
    if(length <= 0 || length1 <= 0){
        return;
    }

    if(arr[length][length1] == 1){
        backstrace(str1, length-1, length1-1, arr);
        System.out.print(str1.charAt(length-1) + " ");
    } else {
        if(arr[length][length1] == 2){
            backstrace(str1, length-1, length1, arr);
        } else {
            backstrace(str1, length, length1-1, arr);
        }
    }
}

0-1バックパックの問題

/**
 *   :       0-1    
 *
 *            dp(n, j)
 * j < wn   0
 * j >= wn  vn
 *           dp(i, j)
 * 0<= j < wi   dp(i+1, j)
 * j >= wi     max{dp(i+1, j), dp(i+1, j-wi)+vi}
 *
 * @Author shilei
 * @Date 5/1
 */
public class DP01Package {
    public static void main(String[] args) {
        int[] w = {8,6,4,2,5};
        int[] v = {6,4,7,8,6};
        int c = 20;
        int[][] dp = new int[w.length][c+1];
        //       0-1    
        func(w, v, c, dp);
        //              
        int[] x = new int[w.length];
        backtrace(w, v, c, dp, x);
    }

    /**
     *          
     * @param w
     * @param v
     * @param c
     * @param dp
     * @param x
     */
    private static void backtrace(int[] w, int[] v, int c, int[][] dp, int[] x) {
        int bestv = 0;

        for(int i=0; i<w.length-1; ++i){
            if(dp[i][c] == dp[i+1][c]){
                x[i] = 0;
            } else {
                x[i] = 1;
                bestv += v[i];
                c -= w[i];
            }
        }

        //    n   
        if(dp[w.length-1][c] > 0){
            bestv += v[w.length-1];
            x[w.length-1] = 1;
        }

        System.out.println(bestv);
        System.out.println(Arrays.toString(x));
    }

    /**
     *   0-1           
     * @param w
     * @param v
     * @param c
     * @param dp
     */
    private static void func(int[] w, int[] v, int c, int[][] dp) {
        int n = w.length - 1;

        //    dp       dp(n, j)
        for(int j=1; j<=c; ++j){
            if(j < w[n]){
                dp[n][j] = 0;
            } else {
                dp[n][j] = v[n];
            }
        }

        //     n-1     
        for(int i=n-1; i>=0; --i){
            for(int j=1; j<=c; ++j){
                if(j < w[i]){
                    dp[i][j] = dp[i+1][j];
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]);
                }
            }
        }
    }
}

ディジタルさんかくけいもんだい
デジタル三角形の問題:デジタル三角宝塔で、最上階から最下層まで歩くことを規定し、各ステップは垂直下、左斜線下、または右斜線下へ行くことができ、最上層から最下層まで行く経路を解き、その経路に沿って通る数字の合計と最大を求め、最大値を出力します.
サンプル入力:1行目は数塔階数N(1<=N<=100)である.2行目から、1つの数字から数塔パターンごとに順次増加し、N層を共有する.5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11サンプル出力:86
この問題は底から上へ再帰的に解くことができる(しかし,多くのサブ問題が繰り返し解くことに注意し,効率が悪い!),コードは次のとおりです.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.println("          :");
    int n = in.nextInt();
    System.out.println("      :");
    int[][] arr = new int[n+1][n+1];
    for(int i=1; i<=n; ++i){
        for (int j = 1; j <= i; j++) {
            arr[i][j] = in.nextInt();
        }
    }

    int max = findMaxPath(arr, 1, 1, n);
    System.out.println("max value:" + max);
}

private static int findMaxPath(int[][] arr, int i, int j, int n) {
    if(i == n || j == 0){
        return arr[i][j];
    } else {
        return Math.max(Math.max(findMaxPath(arr, i+1, j-1, n), findMaxPath(arr, i+1, j, n))
                , findMaxPath(arr, i+1, j+1, n)) + arr[i][j];
    }
}

上の再帰的存在サブ問題は繰り返し解かれる(これは動的計画で解決できる問題の要素の一つではないか.)この問題は角度を変えて考えやすいが,値が最大のデジタルパス,すなわち最適パス上の各数字から始まる下向きのパスもこの数字から最後の層までの最適パスであり,シンボルダイナミックプランニングの第2の基本要素(最適サブ構造原理)であるため,ダイナミックプランニングでこの問題を解決するのに適している.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.println("          :");
    int n = in.nextInt();
    System.out.println("      :");
    int[][] arr = new int[n+1][n+1];
    for(int i=1; i<=n; ++i){
        for (int j = 1; j <= i; j++) {
            arr[i][j] = in.nextInt();
        }
    }

    // dp           
    int[][] dp = new int[n+1][n+1];

    int max = findMaxPath(arr, 1, 1, n, dp);
    System.out.println("max value:" + max);
}

private static int findMaxPath(int[][] arr, int i, int j, int n, int[][] dp) {
    if (i == n || j == 0){
        dp[i][j] = arr[i][j];
        return dp[i][j];
    } else {
        if(dp[i][j] > 0) { //             ，    
            return dp[i][j];
        }

        dp[i][j] = Math.max(Math.max(findMaxPath(arr, i+1, j-1, n, dp)
                , findMaxPath(arr, i+1, j, n, dp))
                , findMaxPath(arr, i+1, j+1, n, dp)) + arr[i][j];
        return dp[i][j];
    }
}

出力結果は次のとおりです.

          :
5
      :
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
max value:86