一.斐波那契数列问题

1.剑指 Offer II 093. 最长斐波那契数列

image.png

本题的难点就是dp数组的定义，要记录这种dp = dp+dp关系的二维数组定义成
以序列倒数第二和倒数第三位下标。例如arr = {2,3,4,5,7,8}，那么dp[3][5] = 4，表示斐式子序列{2,3,5,8}的长度为4。dp[2][4] = 3，表示斐式子序列{3,4,7}的长度为3。
当然这题一开始的思路肯定还是三个for循环来做，但是会超时，解决办法就是使用hash表来帮助我们找到符合arr[i]+arr[k]=arr[j]的那个k,所以hash索引表要记录arr数组的值和下标索引位置的关系。

int max = 0;
        int[][] dp = new int[arr.length][arr.length];
        Map<Integer,Integer> tmp = new HashMap<>();
        for(int i=0;i<arr.length;i++){
            tmp.put(arr[i],i);
        }
        for(int i=0;i<arr.length;i++){
            for(int j=i+2;j<arr.length;j++){
                int k = tmp.getOrDefault(arr[j]-arr[i],-1);
                if(i<k&&k<j){
                    dp[k][j] = dp[i][k]+1;
                    max = Math.max(max,dp[k][j]);
                }
            }
        }
        return max == 0 ? 0 : max + 2;

2.剑指 Offer II 098. 路径的数目

image.png

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] =1;
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j] = dp[0][j-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];
    }
}

剑指 Offer II 099. 最小路径之和

image.png

本题的思路和上一题大致是一样的，先把dp的初值在i为0和jwei0的维度上计算
然后再遍历

public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i=1;i<grid.length;i++){
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<grid[0].length;j++){
            dp[0][j] = dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }

剑指 Offer II 100. 三角形中最小路径之和

image.png

本题的思路和上面题目的差别其实就在三角形的边界上

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        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] = triangle.get(i-1).get(j-1);
            }
        }
        
        int [][] dp = new int[n+1][n+1];
        
        for(int i = 1; i <= n;i++) {
            for(int j = 1; j <= i;j++) {
                if(j == 1)
                    dp[i][j] = arr[i][j] + dp[i-1][j];
                else if(j == i)
                    dp[i][j] = arr[i][j] + dp[i-1][j-1];
                else if(j < i)
                    dp[i][j] = arr[i][j] + Math.min(dp[i-1][j], dp[i-1][j-1]);
                // else 
                //     dp[i][j] = arr[i][j];
            }
        }
        
        int min = dp[n][1];

        for(int i = 1;i <= n;i++ ) {
            if(dp[n][i] < min)
                min = dp[n][i];
        }
        return min;
    }
}

二.字符串匹配问题

image.png

1.剑指 Offer II 095. 最长公共子序列

image.png

定义 dp[i][j]dp[i][j] 表示text1的前 ii个字符和text2的前 jj个字符之间最长 公共子序列 的长度。状态转移方程只需要考虑字符i和j相等以及不想等的情况，看代码吧。

public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for(int i=1;i<text1.length()+1;i++){
            for(int j=1;j<text2.length()+1;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()];
    }

2.剑指 Offer II 096. 字符串交织

本题的dp定义为以i结尾的s1和以j结尾的s2和起来是不是字符串s3。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        //剪枝
        if(s1.length() + s2.length() != s3.length())return false;
        int n = s1.length();
        int m = s2.length();
        boolean[][] dp = new boolean[n+1][m+1];
        //初始化位true
        dp[0][0] = true;
        //初始化s1是否可以直接匹配s3
        for(int i=1;i<n+1;i++){
            dp[i][0] = dp[i-1][0]&&(s1.charAt(i-1) ==s3.charAt(i-1));
        }
        for(int j=1;j<m+1;j++){
            dp[0][j] = dp[0][j-1]&&(s2.charAt(j-1) ==s3.charAt(j-1));
        }
        //交替匹配
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
                dp[i][j] = (dp[i-1][j] && (s1.charAt(i - 1) == s3.charAt(i + j -1)))|(dp[i][j-1] && (s2.charAt(j - 1) == s3.charAt(j + i -1)));
            }
        }


        return dp[n][m];
    }
}

3.最长回文子串

image.png

可能有些人拿到这道题一上手就是暴力解法（然后发现超时），我也是，不过后来发现这道题其实可以用动态规划。思路就是把字符串s逆转，然后求他们的最长连续子串。

class Solution {
   public String longestPalindrome(String s) {
       String s2 = new StringBuffer(s).reverse().toString();
       int dp[][] = new int[s.length()+1][s.length()+1];
       int max = 0;
       int end = 0 ;
       for(int i=1;i<s.length()+1;i++){
           for(int j=1;j<s.length()+1;j++){
               if(s.charAt(i-1)==s2.charAt(j-1)){
                   dp[i][j] = dp[i-1][j-1]+1;
               }
               if (dp[i][j] > max) {
                   max = dp[i][j];
                   end = i; //以 i 位置结尾的字符
               }
           }
       }
       return s.substring(end-max,end);
   }
}

然后会发现其实还是有例子过不去的，如下：

image.png

只能是动用另一种思路了，这时候动态规划来判断一个子串是不是回文串

public class Solution {

    public String longestPalindrome(String s) {
        // 特殊用例判断
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

三.连续问题

152. 乘积最大子数组

image.png

这题是少有的关于连续惩罚的动态规划题目，需要注意的是针对加法的我们发现一般维护一个dp就够了，可是乘法有正负问题，所以要维护两个dp数组，一个维护正的最大值，一个维护负的最大值

class Solution {
    public int maxProduct(int[] nums) {
        if(nums.length == 0)
            return 0;
        int ans = nums[0];
        //两个mDP分别定义为以i结尾的子数组的最大积与最小积；
        int[] maxDP = new int[nums.length];
        int[] minDP = new int[nums.length];
        //初始化DP；
        maxDP[0] = nums[0]; minDP[0] = nums[0];

        for(int i = 1; i < nums.length; i++){
            //最大积的可能情况有：元素i自己本身，上一个最大积与i元素累乘，上一个最小积与i元素累乘；
            //与i元素自己进行比较是为了处理i元素之前全都是0的情况；
            maxDP[i] = Math.max(nums[i], Math.max(maxDP[i-1]*nums[i], minDP[i-1]*nums[i]));
            minDP[i] = Math.min(nums[i], Math.min(maxDP[i-1]*nums[i], minDP[i-1]*nums[i]));
            //记录ans；
            ans = Math.max(ans, maxDP[i]);
        }
        return ans;
    }
}

32. 最长有效括号

image.png

这道题相信大家用普通的暴力思路尝试过后会发现是一定会超时的，这边是一个连续最长的动态规划问题。连续的问题还是一般的数组定义思路——以i位置结尾的最大值，首先是思考状态的转化：
⬇️
1.···((
2.···)(
当索引i的值为(时，dp[i] = 0;
3.·····()
4.·····))
情况三的时候，dp[i]=dp[i-2]+2;
情况四的时候继续考虑
····(·······)) dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2
或者 dp[i] = 0;
或者 dp[i] = 2 +dp[i-1]

class Solution {
/*
    .....((     X
    .....()
    .....))
    .....)(     X
*/
    public int longestValidParentheses(String s) {
        if(s.length() <= 1)     return 0;
        char[] chars = s.toCharArray();
        //dp[i] means from s[0...i] 有效括号, 包含s[i]
        int[] dp = new int[chars.length];
        dp[1] = chars[0] == '(' && chars[1] == ')' ? 2 : 0;

        int max = dp[1];
        for(int i = 2; i < chars.length; i++)
        {
            if(chars[i] == '(')     dp[i] = 0;
            else 
            {
                if(chars[i-1] == '(')
                    dp[i] = dp[i-2] + 2;
                
                else
                {
                    if(i - dp[i-1] - 1 < 0 || chars[i - dp[i-1] -1] == ')')
                        dp[i] = 0;
                    else    
                        dp[i] = i - dp[i-1] - 1 >= 1 ?  2 + dp[i-1] + dp[i - dp[i-1] - 2]: 2 + dp[i-1];
                }
            }

            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

剑指 Offer II 092. 翻转字符

image.png

这题可以直接用常规动态规划写法：

class Solution {
    //dp[i][0]表示前i个元素，最后一个元素为0的最小翻转次数；
    //dp[i][1]表示前i个元素，最后一个元素为1的最小翻转次数
    public int minFlipsMonoIncr(String s) {
        int dp[][]=new int[s.length()][2];
        //初始化
        dp[0][0]=s.charAt(0)=='0'?0:1;
        dp[0][1]=s.charAt(0)=='1'?0:1;
        //状态转移
        for (int i = 1; i <s.length() ; i++) {
            dp[i][0]=dp[i-1][0]+(s.charAt(i)=='0'?0:1);
            dp[i][1]=Math.min(dp[i-1][0],dp[i-1][1])+(s.charAt(i)=='1'?0:1);
        }
        return Math.min(dp[s.length()-1][0],dp[s.length()-1][1]);
    }
}