139. 單詞拆分

dp[i]代表s的前i個(gè)字符是否可以單詞拆分。

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

轉(zhuǎn)移方程：
對(duì)于前i個(gè)字符，只要前面某個(gè)位置j可以被拆分，且j到i截取的子串存在于單詞列表中，那么dp[i] = true。

時(shí)間復(fù)雜度On2，空間復(fù)雜度On。使用把單詞列表先轉(zhuǎn)化為哈希表，使判斷是否存的時(shí)候速度更快。

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

使用回溯， 但是超時(shí)了，只能調(diào)用一下139題的方法進(jìn)行剪枝。
if (set.contains(sub) && wordBreak2(s.substring(i + 1)))
只有后面的字符串能進(jìn)行單詞拆分時(shí)，才符合條件。

原代碼：

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;
    }
}

優(yōu)化后：

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. 乘積最大子數(shù)組

maxDp[i]代表以i為結(jié)尾的子數(shù)組的乘積最大值。
minDp[i]代表以i為結(jié)尾的子數(shù)組的乘積最小值。

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

轉(zhuǎn)移方程：
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數(shù)組十分困難，考慮逆向dp。

dp[i][j]代表從第i行第j列出發(fā)，到達(dá)右下角，初始最低的生命值數(shù)。

邊界：
最右下角的格子，如果數(shù)組大小dungeon[row - 1][col - 1] 小于0，那么所需的最低生命值數(shù)就是它的相反數(shù)加1。 如果大于等于0，那么所需的最低生命值數(shù)是1。
最后一行的某個(gè)位置的dp值，可由它右邊那個(gè)格子的dp值推出。如果dp[i + 1][col - 1] - dungeon[i][col - 1] 大于0，那么就等于這個(gè)數(shù)。如果小于等于0，只要初始生命值為1就行。
最后一列同理。

轉(zhuǎn)移方程：
對(duì)于第i行第j個(gè)格子，考慮往下走還是往右走，肯定是往dp值更小的方向走。
那么dp[i][j] 就等于右邊和下邊的dp較小值減去 dungeon[i][j]，如果這個(gè)值小于等于0，初始生命值為1就行，如果大于0，那么就等于這個(gè)值。

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個(gè)房屋的最高金額。

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

轉(zhuǎn)移方程
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];
    }
}

優(yōu)化：

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

分為兩種情況，偷第一家和不偷第一家。
由于不可能第一家和最后一家都不偷，所以可以把環(huán)形問(wèn)題轉(zhuǎn)化成和212題一樣的問(wèn)題。
偷第一家的時(shí)候，最后一家不能去偷。
不偷第一家的時(shí)候，最后一家可以去偷。
然后取兩者較大值即可。

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列的格子作為正方形最右下頂點(diǎn)的正方形最大邊長(zhǎng)。

邊界：
第一行和第一列的某個(gè)格子如果為0，則dp值為0。如果為1，則dp值為1。

轉(zhuǎn)移方程：
matrix[i][j]如果等于1，則dp[i][j] 與它左邊，上邊，左上 三個(gè)格子有關(guān)。等于三者最小值+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;
    }
}