动态规划、背包问题 6/28 121-124

1.最长回文子序列（ LeetCode 516 ）

动态规划
dp[i][j] i,j之间的最长回文子序列

class Solution {
    
        /* dp[i][j] = 下标i 到 下标j 之间的最长回文子序列长度 初始值 i > j 时dp[i][j] = 0 dp[i][i] = 1 状态转移: 当s[i] = s[j]时，dp[i][j] = dp[i + 1][j - 1] + 2 当s[i] != s[j]时，dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]) */
        public int longestPalindromeSubseq(String s) {
    
            int n = s.length();
            int[][] dp = new int[n][n];
            //状态转移时需要用到下一行的数据，所以会逆着遍历
            for (int i = n - 1; i >= 0; i--) {
    
                dp[i][i] = 1;
                for (int j = i + 1; j < n; 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]);
                }
            }
            return dp[0][n - 1];
        }
    }

2.最长回文子串（ LeetCode 5 ）

方法一：动态规划
参照上一题

 class Solution {
    
        public String longestPalindrome(String s) {
    
            int n = s.length();
            int[][] dp = new int[n][n];
            int ans = 1;
            int[] ansStr = new int[2];
            //状态转移时需要用到下一行的数据，所以会逆着遍历
            for (int i = n - 1; i >= 0; i--) {
    
                dp[i][i] = 1;
                for (int j = i + 1; j < n; 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]);
                    //如果 j - i + 1 == dp[i][j] 成立，则代表i,j范围为回文串，包括i，j
                    if (j - i + 1 > ans && (j - i + 1 == dp[i][j])){
    
                        ans = j - i + 1;
                        ansStr[0] = i;
                        ansStr[1] = j;
                    }
                }
            }
            return s.substring(ansStr[0],ansStr[1] + 1);
        }
    }

方法二：动态规划

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];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
    
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
    
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
    
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
    
                    break;
                }

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

3.目标和（ LeetCode 494 ）

方法一：回溯

class Solution {
    
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
    
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
    
        if (index == nums.length) {
    
            if (sum == target) {
    
                count++;
            }
        } else {
    
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

方法二：动态规划

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
    
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        //dp[i][j]nums前i个数中凑成和为j的组合数
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
    
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
    
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
    
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

4.最后一块石头的重量 II（ LeetCode 1049 ）

方法一：动态规划 01背包
朴素数组

class Solution {
    
    public int lastStoneWeightII(int[] ss) {
    
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[][] f = new int[n + 1][t + 1];
        for (int i = 1; i <= n; i++) {
    
            int x = ss[i - 1];
            for (int j = 0; j <= t; j++) {
    
                f[i][j] = f[i - 1][j];
                if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
            }
        }
        return Math.abs(sum - f[n][t] - f[n][t]);
    }
}

方法二：01背包 滚动数组优化

class Solution {
    
    public int lastStoneWeightII(int[] ss) {
    
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[][] f = new int[2][t + 1];
        for (int i = 1; i <= n; i++) {
    
            int x = ss[i - 1];
            int a = i & 1, b = (i - 1) & 1;
            for (int j = 0; j <= t; j++) {
    
                f[a][j] = f[b][j];
                if (j >= x) f[a][j] = Math.max(f[a][j], f[b][j - x] + x);
            }
        }
        return Math.abs(sum - f[n&1][t] - f[n&1][t]);
    }
}

方法三：01背包 一维数组优化

class Solution {
    
    public int lastStoneWeightII(int[] ss) {
    
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[] f = new int[t + 1];
        for (int i = 1; i <= n; i++) {
    
            int x = ss[i - 1];
            for (int j = t; j >= x; j--) {
    
                f[j] = Math.max(f[j], f[j - x] + x);
            }
        }
        return Math.abs(sum - f[t] - f[t]);
    }
}