动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int backage(int[] weights, int w) {
    int n = weights.length;
    // 这里都+1是为了考虑i-1不会越界的情况
    int[][] dp = new int[n + 1][w + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j >= weights[i - 1]) {
                dp[i][j] = Math.max(dp[i - 1][j - weights[i - 1]] + weights[i - 1], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][w];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int getMoreGold(int weight, int[] costs, int[] weights) {
    int[] tmp = new int[weight + 1];
    int[] result = new int[weight + 1];

    for (int i = 0; i < weights.length; i++) {
        // 内层循环为人,一行从左到右一个一个算,也就是逐渐增加人数
        for (int j = 0; j <= weight; j++) {
            if (weights[i] <= j) {
                result[j] = Math.max(tmp[j], costs[i] + tmp[j - weights[i]]);
            }
        }
        tmp = result.clone();
    }
    return result[result.length - 1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int longestValidParentheses(String s) {
    int maxans = 0;
    int dp[] = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                dp[i] = dp[i - 1] + 
                  ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = Math.max(maxans, dp[i]);
        }
    }
    return maxans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int calculateMinimumHP(int[][] dungeon) {
    int rowLen = dungeon.length;
    int colLen = dungeon[0].length;
    int[][] blood = new int[rowLen][colLen];
    for (int i = colLen - 1; i >= 0; i--) {
        for (int j = rowLen - 1; j >= 0; j--) {
            if (i == rowLen - 1 && j == colLen - 1) {
                blood[i][j] = dungeon[i][j];
            } else if (i == rowLen - 1) {
                blood[i][j] = blood[i][j + 1] + dungeon[i][j];
            } else if (j == colLen - 1) {
                blood[i][j] = blood[i + 1][j] + dungeon[i][j];
            } else {
                blood[i][j] = Math.max(blood[i + 1][j], blood[i][j + 1]) + dungeon[i][j];
            }
            // 最多为不扣血
            blood[i][j] = Math.min(0, blood[i][j]);
            int i1 = 1 - blood[i][j];
            System.out.print(dungeon[i][j] + "(" + i1 + ")  ");
        }
        System.out.println();
    }
    return 1 - blood[0][0];
}

1
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private boolean isMatchR(String text, String pattern) {
    // 多一维的空间，因为要考虑两边为空的情况进行匹配(这就是动态规划中的特殊情况处理, 在判断的时候会用到这些特殊情况)
    // 当然如果text不为空, p为空则肯定匹配不上, 所以可以忽略, 因为定义的数组默认都是False
    // dp[i][j]dp[i][j]表示 text 从 i 开始到最后，pattern 从 j 开始到最后，此时 text 和 pattern 是否匹配。
    boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
    // dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。
    dp[text.length()][pattern.length()] = true;

    // 为什么text要从len开始减少, 是因为要匹配一圈text为空的情况.
    for (int i = text.length(); i >= 0; i--) {
        for (int j = pattern.length() - 1; j >= 0; j--) {
            boolean first_match = i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.');
            if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
            } else {
                dp[i][j] = first_match && dp[i + 1][j + 1];
            }
        }
        System.out.println();
    }
    return dp[0][0];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private boolean isMatchS(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        // sl/pl 代表的是长度, 因为要考虑长度为0的情况
        // i,j代表的是字符匹配到的位置
        // dp[sl][pl] 代表长度为sl,pl之前都可以匹配 -> 状态
        // sl,pl 长度都为0可以匹配 -> 特殊1
        // p为空 s不为空肯定都匹配不上 所以要考虑s为空p不为空的所有情况 s从长度为0开始循环 -> 特殊2
        for (int sl = 0; sl <= s.length(); sl++) {
            for (int pl = 1; pl <= p.length(); pl++) {
                int i = sl - 1, j = pl - 1;
                if (sl == 0) {
                    dp[sl][pl] = p.charAt(j) == '*' && dp[sl][pl - 2];
                } else if (p.charAt(j) == '*') {
                    boolean singleMatch = s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.';
                    dp[sl][pl] = singleMatch && dp[sl - 1][pl] || dp[sl][pl - 2];
                } else {
                    boolean singleMatch = s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
                    dp[sl][pl] = singleMatch && dp[sl - 1][pl - 1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String longestPalindrome(String s) {
    int length = s.length();
    boolean[][] P = new boolean[length][length];
    int maxLen = 0;
    String maxPal = "";
    for (int len = 1; len <= length; len++) //遍历所有的长度
        for (int start = 0; start < length; start++) {
            int end = start + len - 1;
            //下标已经越界，结束本次循环
            if (end >= length) break;
            //长度为 1 和 2 的单独判断下
            P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1])
                    && s.charAt(start) == s.charAt(end); 
            if (P[start][end] && len > maxLen) {
                maxPal = s.substring(start, end + 1);
            }
        }
    return maxPal;
}