动态规划题集

LeetCode2369

​ 本题的状态定义为dp[i + 1]表示下标0-i的子数组是否可以是有效划分，状态转移方案为

      1. nums[i] == nums[i - 1],问题就转化为查看0-(i-2)的子数组是否是有效划分，根据状态定义就是dp[i - 1]
      2. nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2],问题就转化为查看0-(i - 3)的子数组是否是有效划分，根据状态定义就是dp[i - 2]
      3. nums[i] == nums[i - 1] + 1 && nums[i - 1] == nums[i - 2] + 1,问题就转化为查看0-(i - 3)的子数组是否是有效划分，根据状态定义就是dp[i - 2]

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        //dp[i + 1]表示0-i的子数组是否为有效划分
        boolean dp[] = new boolean[n + 1];
        dp[0] = true;

        for(int i = 1; i < n; i ++){
            if(dp[i - 1] && nums[i] == nums[i - 1] || i > 1 && dp[i - 2] && (
                nums[i - 2] == nums[i - 1] && nums[i - 1] == nums[i] || 
                nums[i - 1] == nums[i - 2] + 1 && nums[i] == nums[i - 1] + 1
            )){
                dp[i + 1] = true;
            }   
        }
        return dp[n];
    }
}

模拟样例：nums[4,4,4,5,6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
i = 1:
	dp[i-1]=dp[0]:true;
	nums[i] == nums[i-1]=4;
	dp[2] = true;
i = 2:
	dp[i-1]=dp[1]:false;
	dp[i-2]=dp[0]:true;
	nums[i-2]=nums[i-1]=nums[i]=4;
	dp[3] = true;
i = 3:
	dp[i-1]=dp[2]=true,nums[i] != nums[i-1];
	dp[i-2]=dp[1]:false;
i = 4:
	dp[i-1]=dp[3]=true,nums[i] != nums[i-1];
	dp[i-2]=dp[2]=true;
	nums[i - 1] == nums[i - 2] + 1 && nums[i] == nums[i - 1] + 1;
	dp[4] = true;
return dp[4];

LeetCode5

​ 本题要我们求解给定字符串的最长回文子串，最暴力的做法就是遍历每个子串并判断是否为回文串，这种做法需要遍历两个自由度，并且判断子串是否为回文串也需要O(n)的时间复杂度，因此总的时间复杂度为O(n^3^)，会超时。

​ 一般遇到这种字符串的题目以及求解最大值最小值方案数，并且数据范围比较大的题，都需要通过动态规划来优化。但是很多人(包括我)都能想到是用动态规划解答，但是不知道如何定义状态，以及如何建立状态转移方程，因此只能干瞪眼，其实最佳做法就是直接去看题解，学习人家是如何定义状态的，以及状态是如何转移的，这样才是最高效的。只有刷了一定的题，有了经验后，或许下次遇到动态规划的题能够成功定义出状态以及建立状态转移方程。

​ 言归正传，看了人家的题解后，人家定义的状态是dp[i] [j]：表示[i,j]这个子串是否是回文串(我当时定义的状态是dp[i]：表示[0,i]这个子串是否是回文串，显然是有问题的，因为我这种定义将一个子串的头定死在了开头，这只是所有子串的一部分)。而[i,j]这个子串是否为回文串，可以由[i+1,j-1]这个子串推出，因为如果[i+1，j-1]这个子串是回文串的话，那么只需要保证s[i]==s[j]就可以判断[i,j]这个子串是否为回文串。(在构建转移方程时，往往将前一个状态作为切入点，经常可以见到dp[i] = dp[i - 1] + …，这也是动态规划比较快的原因：利用了之前求得的数据)。

dp[i,j] = dp[i+1,j-1] && s[i] == s[j]

​ 这里有两个特殊点需要特判，当子串长度为1和2时，比如[1,1],[1,2]。如果按照上述转移方程，需要判断dp[2] [0]和dp[2] [1],由于我们的状态定义需要保证i < j，因此这两个状态不会更新，将会导致所有长度为1，2的子串的dp值都是false，这显然是不对的。因此最终的状态转移方程：

dp[i,j] = true, i == j；

dp[i,j] = s[i] == s[j],j == i + 1;

dp[i,j] == dp[i+1,j-1] && s[i] == s[j]

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean dp[][] = new boolean[n][n];

        int maxLen = 0;
        String res = "";
        for(int len = 1; len <= n; len ++){
            for(int start = 0; start < n; start ++){
                int end = start + len - 1;
                if(end >= n){
                    break;
                }
                dp[start][end] = (len == 1 || len == 2 || dp[start + 1][end - 1]) && (s.charAt(start) == s.charAt(end));
                if(dp[start][end] && len > maxLen){
                    maxLen = len;
                    res = s.substring(start,end + 1);
                } 
            }
        }

        return res;
    }
}

时间复杂度：$O(n^2)$