Lecture on linear dynamic programming

Special lecture on linear dynamic programming

Linear programming concept

The main feature of dynamic programming is that the derivation of state is based on the problem scale $i$ From small to large （ Or push it all the way from the back , such as 「 Stone game 」、「2140. Solve intellectual problems 」 It is pushed from the back to the front ), The solution of the larger scale problem depends on the solution of the smaller scale problem .

Generally, the steps to solve such problems are as follows ：

• Sure $dp[i]$ The meaning of representation / attribute
• According to the meaning of the title , Find the corresponding State transition equation
• Determine the initial value
  • If it's from front to back , Then you need to make sure $dp[0]$ perhaps $dp[1]$
  • If it is from the back to the front , Then you need to make sure $dp[n]$ perhaps $dp[n-1]$

LeetCode 877. Stone game

class Solution {
    
    public boolean stoneGame(int[] piles) {
    
        int n = piles.length;
        long[][] dp = new long[n + 1][n + 1];
        // dp[i][j] Representative slave interval [i,j] The maximum score obtained between 
        // dp[i][j] = Math.max(piles[i] + dp[i + 1][j], dp[i][j - 1] + plies[j])
        // dp[i][i] = 0
        // dp[0][n - 1] > 0 ? true : false;
        for (int i = 0 ; i < n; i++) {
    
            dp[i][i] = 0;
        }
        for (int i = n - 1; i >= 0; i--) {
    
            for (int j = i + 1; j < n; j++) {
    
                dp[i][j] = Math.max(piles[i] + dp[i + 1][j], dp[i][j - 1] + piles[j]);
            }
        }
        return dp[0][n - 1] > 0 ? true : false;
    }
}

LeetCode 2140. Solve intellectual problems

class Solution {
    
    public long mostPoints(int[][] q) {
     
        int n = q.length;
        // dp[i] The meaning of is from the subscript i~n-1 The maximum score obtained 
        // dp[i] = Math.max(dp[Math.min(n, q[i][1])] + q[i][0], dp[i])
        long[] dp = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
    
            dp[i] = Math.max(dp[Math.min(n, i + q[i][1] + 1)] + q[i][0], dp[i + 1]);
        }
        return dp[0];
    }
}

LeetCode 72. Edit distance

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        int n = word1.length();
        int m = word2.length();
        //  meaning ：dp[i][j] representative Word1 From the subscript 0~i and word2 From the subscript 0~j The minimum number of operations used 
        //  State transition equation ：dp[i][j] = Math.min(dp[i -1][j] + 1,Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + (word1.charAt(i - 1) != word2.charAt(j - 1) ? 1 : 0)));
        int[][] dp = new int[n + 1][m + 1];
        if (n * m == 0) {
    
            return n + m;
        }
        for (int i = 0; i <= n; i++) {
    
            dp[i][0] = i;
        }
        for (int j = 0 ; j <= m ; j++) {
    
            dp[0][j] = j;
        }
        for (int i = 1; i <= n; i++) {
    
            for (int j = 1; j <= m; j++) {
    
                int left = dp[i  -1][j] + 1;
                int down = dp[i][j - 1] + 1;
                int left_down = dp[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
    
                    left_down++;
                }
                dp[i][j] = Math.min(left_down, Math.min(left, down));
            }
        }
        return dp[n][m];
    }
}