动态规划day09

718. 最长重复子数组

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        int res = 0;
        //dp[0][0]代表无元素
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > res) res = dp[i][j];
            }
        }
        return res;

    }
}

//滚动数组
// class Solution {
//     public int findLength(int[] nums1, int[] nums2) {
//         int len1 = nums1.length, len2 = nums2.length;
//         if (len1 == 0 || len2 == 0) return 0;
//         int[] dp = new int[len2 + 1];
//         int res = 0;
//         //dp[0][0]代表无元素
//         for (int i = 1; i <= len1; i++) {
//             //要从后向前遍历 否则会覆盖上一层结果
//             for (int j = len2; j >= 1; j--) {
//                 if (nums1[i - 1] == nums2[j - 1]) {
//                     dp[j] = dp[j - 1] + 1;
//                 } else {
//                     dp[j] = 0;
//                 }
//                 if (dp[j] > res) res = dp[j];
//             }
//         }
//         return res;

//     }
// }

1143. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] a1 = text1.toCharArray(), a2 = text2.toCharArray();
        int[][] dp = new int[a1.length + 1][a2.length + 1];
        //dp[0][0]代表无元素
        for (int i = 1; i <= a1.length; i++) {
            for (int j = 1; j <= a2.length; j++) {
                if (a1[i - 1] == a2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[a1.length][a2.length];
    }
}

1035. 不相交的线

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        /* 1  1
         * 4  2
         * 2  4
         * 上述这样连不相交的线 与最长重复子数组问题相同（1035）
         */
         int len1 = nums1.length, len2 = nums2.length;
         int[][] dp = new int[len1 + 1][len2 + 1];
         //dp[0][0]代表无元素
         for (int i = 1; i <= len1; i++) {
             for (int j = 1; j <= len2; j++) {
                 if (nums1[i - 1] == nums2[j - 1]) {
                     dp[i][j] = dp[i - 1][j - 1] + 1;
                 } else {
                     dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                 }
             }
         }
         return dp[len1][len2];
    }
}

53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (res < dp[i]) res = dp[i];
        }
        return res;
    }
}

392. 判断子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] a1 = s.toCharArray(), a2 = t.toCharArray();
        int[][] dp = new int[a1.length + 1][a2.length + 1];
        //dp[0][0]代表无元素
        for (int i = 1; i <= a1.length; i++) {
            for (int j = 1; j <= a2.length; j++) {
                if (a1[i - 1] == a2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //最终符合题意的只能是t.length() >= s.length()，所以最长公共子序列的最大值只可能在dp[i][j - 1]中产生
                    //dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        //最长公共子序列是否为s
        return a1.length == dp[a1.length][a2.length];
    }
}