day53|1143.最长公共子序列、1035.不相交的线、53. 最大子序和

一、1143.最长公共子序列

注意的点：

1. 比较两个字符串的字符，若相等，就在左上角（i-1、j-1） 的基础上+1。若不相等，则就取左方（i、j-1）和上方（i-1、j）的最大值。
2. dp数组设置成 长度+1 ，因为这样的话容易初始化（全部设为0就行）。

以下是代码部分：

public class 最长公共子序列1143 {

    public int longestCommonSubsequence(String text1, String text2) {

        //典型的二维dp数组
        //这里要注意都是 +1
        //这个数组就表示的是i、j之前的最长公共子序列
        int[][] dp = new int[text1.length()+1][text2.length()+1];

        //初始化
        for (int i = 0; i < text1.length()+1; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < text2.length()+1; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i < text1.length()+1; i++) {
            for (int j = 1; j < text2.length()+1; j++) {

                //如果字符相同，就 +1
                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()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二、1035.不相交的线

与上一题的思路完全一样，只不过是以图像的形式呈现问题。

三、53. 最大子序和

注意的点：

1. 其实用动态规划与贪心算法的思想是一样的，当前一片区域加到即将成为负数的时候，放弃继续加入新的元素。重新开启下一片区域。
2. 每次加入一个新元素，都要与全局最优解比较哪个更大

以下是代码部分：

public class 最大子数组和53 {

    public int maxSubArray(int[] nums) {

        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        int result = dp[0];

        for (int i =1; i < nums.length; i++) {

            if(dp[i-1] < 0)
                dp[i] = nums[i];
            else
                dp[i] = dp[i-1] + nums[i];

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

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22