516. 最长回文子序列

516. 最长回文子序列

对于大部分子序列和子串的问题采用动态规划问题。
看到题目一开始想到的是一维数组来做dp，显然没办法做。
dp[i][j]表示i到j最大的子序列的最长回文数。

                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }

要根据转移方程来写循环，观察到i要用到更大的i做基础。因此从s.length开始，然后减减。
观察到j要用到更小的，所以++，因为j要比i大，所以从i开始。
答案如下：

    public int longestPalindromeSubseq(String s) {
        int dp[][] = new int[s.length()][s.length()];
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if(j == i) {
                    dp[i][j] = 1;
                } else if(j == i+1) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = 2;
                    } else {
                        dp[i][j] = 1;
                    }
                } else if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][s.length()-1];
    }

今天还做了一道简单题如下：

551. 学生出勤记录 I

显然可以通过动态规划来做：

    public boolean checkRecord(String s) {
        int n = 0;
        int m = 0;
        if(s.charAt(0) == 'L') n = 1;
        if(s.charAt(0) == 'A') m++;
        for(int i=1; i<s.length(); i++) {
            if(s.charAt(i) == 'A') {
                m++; 
            }
            if(s.charAt(i) == 'L') {
                n++;
                if(n == 3) {
                    return false;
                }
            } else {
                n = 0;
            }
        }
        if(m>=2) {
            return false;
        }
        return true;
    }