LeetCodeダイナミックプランニング

動的計画とは
以下は私が動的計画の特徴を総合して与えた動的計画の定義です.
動的計画は多段階決定最適解モデルであり、一般的に最値問題を求めるために用いられ、多くの場合、下から上への繰返し方式を用いて各サブ問題の最適解(すなわち最適サブ構造)を導出し、さらに自然に依存子問題の原問題の最適解を導出することができる.
 
重点を置く:
 
多段階の決定は、問題がサブ問題、サブ問題に分解できることを意味します...すなわち,問題は複数のサブ問題に分割して解くことができる.
最適サブ構造は,下から上への繰返し過程において,我々が求めた各サブ問題は必ずグローバル最適解であり,その分解サブ問題がグローバル最適解である以上,それらの解に依存する原問題も自然にグローバル最適解である.
下から上へ、どのようにして下から上へ各サブ問題の最適解を求めることができますか?サブ問題の間に一定の関連があることを肯定することができます.すなわち、反復繰返し式も「状態遷移方程式」と呼ばれ、この状態遷移方程式を定義するには、各サブ問題の状態(DP状態)を定義する必要があるが,なぜ下から上へ解くのか,再帰のような上から下への解法を採用すると,サブ問題の間に大量の重なりが存在する可能性があり,大量の重なりサブ問題は大量に計算を繰り返すことを意味し,時間的複雑度が指数関数的に上昇する可能性が高いからである.(以下では、このような繰り返し計算による指数級の時間的複雑さが複数見られる)ので、下から上への解法は重複するサブ問題を解消することができる.
 
上ではわかりにくいかもしれませんが、重要なのはステータスとポリシーを理解することです.ステータスは現在の結果に関連する定義であり、ポリシーは現在のステータスを変更する方法であり、すべてのポリシーを巡って最適なポリシーを選択することです.物理的なMaxまたはMin.
 
LeetCode 62. 異なるパス
dp[i][j]はiを表し、j位置にはいくつの歩き方があり、すべての初期状態dp[i][0]=1、dp[0][i]=1である.
上から下へ行くか、左から右へ行くしかないので、すべてのダイナミック転送:

dp[i][j]=dp[i][j-1]+dp[i-1][j]

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i

 
LeetCode 63. 異なるパスII
条件付きダイナミックプランニングは,前の問題に基づいて障害条件をうまく処理する.
 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i

LeetCode 64. 最小パスと
 
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        int temp=0;
        for(int i=0;i

 
LeetCode 300. 最長上昇サブシーケンス
動的計画の基礎問題,dp[i]はnum[i]で終わる最長上昇サブシーケンスがどれだけであるかを示す.
状態遷移方程式はnum[j]
dp[i]=Math.max(dp[i],dp[j]+1);

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int result = 0;
        for(int i=0;iresult){
                result = dp[i];
            }
        }
        return result;
    }
}

72.距離の編集
古典的なテーマは距離を編集して、トップからプラスする考え方は比較的に動的な移行方程式を理解しやすいです.
s 1[i]==s 2[j]何もしないときdp(i-1,j-1)
その他の3つのケースは、置換、削除、挿入
dp[i-1][j-1]
dp[i][j-1]
dp[i-1][j]

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++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

91.復号方法
条件と状態の問題をよく探します.
 

class Solution {
   public int numDecodings(String s) {
        int[] dp = new int[s.length()];
        if(s.charAt(0)=='0'){
            return 0;
        }
        dp[0]=1;
        for(int i=1;i

 
LeetCode 56. マージ区間
欲張りアルゴリズムは、まず配列を並べて、それから最初に始めたものを取ります.ルールに従ってマージします.

class Solution {
     class Interval {
        int startinter;
        int endinter;
    }
    public int[][] merge(int[][] intervals) {
        
        if(intervals==null||intervals.length==0){
            return intervals;
        }
        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        List intervalList = new ArrayList<>();
        int startinter = intervals[0][0];
        int endinter = intervals[0][1];
        for(int i=1;iendinter){
                Interval interval = new Interval();
                interval.endinter=endinter;
                interval.startinter=startinter;
                intervalList.add(interval);
                startinter = intervals[i][0];
                endinter = intervals[i][1];
            }else {
                if (startinter > intervals[i][0]) {
                    startinter = intervals[i][0];
                }
                if (endinter < intervals[i][1]) {
                    endinter = intervals[i][1];
                }
            }
        }
        Interval interval = new Interval();
        interval.endinter=endinter;
        interval.startinter=startinter;
        intervalList.add(interval);
       int[][] result = new int[intervalList.size()][2];
        for(int i=0;i

 
486.予測勝者
 

class Solution {
     class Node {
        int fir;
        int sec;
    }


    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if(n==1)
            return true;
        Node[][] dp = new Node[n][n];
        for(int i=0;i=0;i--){
            for (int j = i+1;j right){
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i+1][j].fir;
                }else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j-1].fir;
                }
            }
        }
        return dp[0][n-1].fir >= dp[0][n-1].sec;
    }
}