题目一：鸡蛋掉落

解法一

状态：当前拥有的鸡蛋数 和 需要测量的楼层数

选择：选择去哪层楼扔鸡蛋

结果：最坏情况下扔鸡蛋的次数

MyMap map = new MyMap(); //备忘录map，防止重复计算

public int superEggDrop(int egg, int level) {
    if (egg == 1) return level;
    if (level == 0) return 0;

    if (map.get(egg, level) != null)
        return map.get(egg, level);

    int res = Integer.MAX_VALUE;
    //穷举所有可能的情况
    for (int i = 1; i <= level; i++) {
        res = Math.min(res, Math.max(
                superEggDrop(egg, level - i), //没碎
                superEggDrop(egg - 1, i - 1)  //碎了
        ) + 1);
    }
    map.put(egg, level, res);
    return res;
}

static class MyMap extends HashMap<String, Integer> {
    public void put(Integer key1, Integer key2, Integer value) {
        super.put(key1 + "," + key2, value);
    }

    public Integer get(Integer key1, Integer key2) {
        return super.get(key1 + "," + key2);
    }
}

解法二

将解法一通过二分优化

MyMap map = new MyMap();

public int superEggDrop(int egg, int level) {
    if (egg == 1) return level;
    if (level == 0) return 0;

    if (map.get(egg, level) != null)
        return map.get(egg, level);

    int res = Integer.MAX_VALUE;
    int left = 1, right = level;
    while (left <= right) {
        int mid = (left + right) / 2;
        int broken = superEggDrop(egg - 1, mid - 1); //碎了
        int notBroken = superEggDrop(egg, level - mid); //没碎

        if (broken > notBroken) {
            right = mid - 1;
            res = Math.min(res, broken + 1);
        } else {
            left = mid + 1;
            res = Math.min(res, notBroken + 1);
        }
    }

    map.put(egg, level, res);
    return res;
}

static class MyMap extends HashMap<String, Integer> {
    public void put(Integer key1, Integer key2, Integer value) {
        super.put(key1 + "," + key2, value);
    }

    public Integer get(Integer key1, Integer key2) {
        return super.get(key1 + "," + key2);
    }
}

解法三

状态：当前鸡蛋的个数 和 最多允许的扔鸡蛋的次数

选择：碎了 、 没碎

结果：总楼层数

状态转移方程：dp[egg][cnt] = dp[egg-1][cnt-1] + dp[egg][cnt] + 1

public int superEggDrop(int egg, int level) {
    int[][] dp = new int[egg + 1][level + 1];

    int m = 0;
    while (dp[egg][m] < level) {
        m++;
        for (int k = 1; k <= egg; k++) {
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
    }
    return m;
}

题目二：戳气球

状态：位置i和j (戳破i和j之间的所有气球，不包括i和j)

选择：位置i和j之间的k(最后一个戳破的气球，i<k<j)

结果：最大金币

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] a = new int[n + 2];
    a[0] = a[n + 1] = 1; //将nums数组两边边界设为1
    for (int i = 1; i <= n; i++) a[i] = nums[i - 1];

    int[][] dp = new int[n + 2][n + 2];
    for (int i = n; i >= 0; i--) {
        for (int j = i + 2; j <= n + 1; j++) {
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                        dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); //状态方程
            }
        }
    }

    return dp[0][n + 1];
}

题目三：背包问题

状态：背包的容量、可选择的物品(可反向用已选择前i个物品来表示)

选择：装进背包与不装进背包

结果：装进背包的物品的最大价值

public int bag01(int[] weight, int[] value, int capacity) {
    int cnt = weight.length; //物品的数量
    int[][] dp = new int[cnt + 1][capacity + 1];

    for (int i = 1; i <= cnt; i++) { //状态：已选择前i个物品
        for (int j = 1; j <= capacity; j++) { //状态：背包的容量
            if (weight[i] < j) { //重量大于背包容量，不能装
                dp[i][j] = dp[i - 1][j];
            } else {
                //装或不装，择优
                dp[i][j] = Math.max(dp[i - 1][j], //不装
                        dp[i - 1][j - weight[i]] + value[i]); //装
            }
        }
    }

    return dp[cnt][capacity];
}

3.2 子集背包问题

状态：背包的容量、可选择的物品(可反向用已选择前i个物品来表示)
选择：装进背包与不装进背包
结果：是否恰好装满

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 == 1) return false;
    int capacity = sum / 2; //一半容量
    int cnt = nums.length;
    boolean[][] dp = new boolean[cnt + 1][capacity + 1];

    for (int i = 0; i <= cnt; i++) dp[i][0] = true;

    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    return dp[cnt][capacity];
}

3.3 零钱兑换

public int coinChange(int[] coins, int amount) {
    final int ERROR = Integer.MAX_VALUE - 10003;
    int cnt = coins.length;

    int[][] dp = new int[cnt + 1][amount + 1];

    for (int i = 1; i <= amount; i++) dp[0][i] = ERROR;

    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= amount; j++) {
            if (coins[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j],
                        dp[i][j - coins[i - 1]] + 1);
            }
        }
    }

    return dp[cnt][amount] >= ERROR ? -1 : dp[cnt][amount];
}

3.4 零钱兑换 II

/**
 * 背包问题
 * dp[i][j]: i:物品个数 j:背包容量 value:种数
 */
public int change(int amount, int[] coins) {
    int cnt = coins.length;

    int[][] dp = new int[cnt + 1][amount + 1];

    for (int i = 0; i <= cnt; i++) dp[i][0] = 1;

    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= amount; j++) {
            if (coins[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j]  //不动
                        + dp[i][j - coins[i - 1]]; //添加硬币
            }
        }
    }

    return dp[cnt][amount];
}

四、区间dp

4.1 切棍子的最小成本

这道题是经典的区间dp。类似石子合并问题、戳气球。
切分木棍也可以想象成每次合并相邻的木棍，使得总成本最小。

  • 状态dp[i][j]：

    • 集合：所有把[i,j]的木棍合成一根的方案

    • 属性：求这些方案的最小成本。

  • 状态计算：
    最后的合并位置是k
    dp[i][j] = min(dp[i, k] + dp[k, j] + cost)

public int minCost(int n, int[] cuts) {
    List<Integer> list = new ArrayList<>();
    list.add(0);
    list.add(n);
    for (int num : cuts) list.add(num);
    Collections.sort(list);

    int m = list.size();
    int[][] dp = new int[m][m];
    for (int len = 2; len <= n; len++) { //枚举区间
        for (int i = 0; i + len < m; i++) { //枚举左端点
            int j = i + len; //右端点
            //状态转移
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + list.get(j) - list.get(i));
            }
        }
    }
    return dp[0][m - 1];
}

hhhhh