Leetcode动态规划II

139. 单词拆分

dp[i]代表s的前i个字符是否可以单词拆分。

边界：
空字符串可以拆分，dp[0] = true

转移方程：
对于前i个字符，只要前面某个位置j可以被拆分，且j到i截取的子串存在于单词列表中，那么dp[i] = true。

时间复杂度On2，空间复杂度On。使用把单词列表先转化为哈希表，使判断是否存的时候速度更快。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

140. 单词拆分 II

使用回溯，但是超时了，只能调用一下139题的方法进行剪枝。
if (set.contains(sub) && wordBreak2(s.substring(i + 1)))
只有后面的字符串能进行单词拆分时，才符合条件。

原代码：

class Solution {
    List<String> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    Set<String> set;

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String str : temp) {
                sb.append(str + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
            return;
        }
        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (set.contains(sub)) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        dfs(0, s);
        return res;
    }
}

优化后：

class Solution {
    List<String> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    Set<String> set;

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String str : temp) {
                sb.append(str + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
            return;
        }
        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (set.contains(sub) && wordBreak2(s.substring(i + 1))) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    //第139题的方法
    public boolean wordBreak2(String s) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        dfs(0, s);
        return res;
    }
}

152. 乘积最大子数组

maxDp[i]代表以i为结尾的子数组的乘积最大值。
minDp[i]代表以i为结尾的子数组的乘积最小值。

边界：
maxDp[0] = minDp[0] = nums[0]

转移方程：
maxDp[i]取以下三者较大值： nums[i]本身，maxDp[i - 1] * nums[i] 和 minDp[i - 1] * nums[i]。
minDp[i]取以下三这较小值： nums[i]本身，maxDp[i - 1] * nums[i] 和 minDp[i - 1] * nums[i]。

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

174. 地下城游戏

这道题从左上往右下遍历，求解dp数组十分困难，考虑逆向dp。

dp[i][j]代表从第i行第j列出发，到达右下角，初始最低的生命值数。

边界：
最右下角的格子，如果数组大小dungeon[row - 1][col - 1] 小于0，那么所需的最低生命值数就是它的相反数加1。如果大于等于0，那么所需的最低生命值数是1。
最后一行的某个位置的dp值，可由它右边那个格子的dp值推出。如果dp[i + 1][col - 1] - dungeon[i][col - 1] 大于0，那么就等于这个数。如果小于等于0，只要初始生命值为1就行。
最后一列同理。

转移方程：
对于第i行第j个格子，考虑往下走还是往右走，肯定是往dp值更小的方向走。
那么dp[i][j] 就等于右边和下边的dp较小值减去 dungeon[i][j]，如果这个值小于等于0，初始生命值为1就行，如果大于0，那么就等于这个值。

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length, col = dungeon[0].length;
        int[][] dp = new int[row][col];
        if (dungeon[row - 1][col - 1] < 0) {
            dp[row - 1][col - 1] = -dungeon[row - 1][col - 1] + 1;
        } else {
            dp[row - 1][col - 1] = 1;
        }
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = Math.max(1, dp[i + 1][col - 1] - dungeon[i][col - 1]);
        }
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = Math.max(1, dp[row - 1][j + 1] - dungeon[row - 1][j]);
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
}

198. 打家劫舍

dp[i]代表偷前i个房屋的最高金额。

边界：
dp[0] = nums[0]

转移方程
dp[i] = max(dp[i-2] + nums[i] , dp[i-1])

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

优化：

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int p = 0, q = nums[0], r = nums[0];
        for (int i = 1; i < nums.length; i++) {
            r = Math.max(p + nums[i], q);
            p = q;
            q = r;
        }
        return r;
    }
}

213. 打家劫舍 II

分为两种情况，偷第一家和不偷第一家。
由于不可能第一家和最后一家都不偷，所以可以把环形问题转化成和212题一样的问题。
偷第一家的时候，最后一家不能去偷。
不偷第一家的时候，最后一家可以去偷。
然后取两者较大值即可。

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];//偷第一家
        for (int i = 1; i < nums.length; i++) {
            if (i == nums.length - 1) {//最后一家不能偷
                dp[i] = dp[i - 1];
            }
            dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
        }
        int res = dp[nums.length - 1];
        Arrays.fill(dp, 0);
        dp[0] = 0;//不偷第一家
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
        }
        res = Math.max(res, dp[nums.length - 1]);
        return res;
    }
}

221. 最大正方形

dp[i][j]代表以第i行第j列的格子作为正方形最右下顶点的正方形最大边长。

边界：
第一行和第一列的某个格子如果为0，则dp值为0。如果为1，则dp值为1。

转移方程：
matrix[i][j]如果等于1，则dp[i][j] 与它左边，上边，左上三个格子有关。等于三者最小值+1。
matrix[i][j]如果等于0，则dp[i][j] = 0

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length, col = matrix[0].length;
        int[][] dp = new int[row][col];
        int res = 0;
        for (int i = 0; i < row; i++) {
            dp[i][0] = matrix[i][0] == '0' ? 0 : 1;
            res = Math.max(res, dp[i][0]);
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = matrix[0][j] == '0' ? 0 : 1;
            res = Math.max(res, dp[0][j]);
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res * res;
    }
}