动态规划-区间DP

zhilu   in 杭州

# 区间DP

# 定义

区间类动态规划是线性规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值， 那么

f(i,j)= max \{ f(i,k) + f(k+1,j) + cost \}

cost 为将这两组元素合并起来的代价

# 性质

区间 DP 有以下特点：

  • 合并：即将两个或多个部分进行整合，当然也可以反过来；
  • 特征：能将问题分解为能两两合并的形式；
  • 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

# 问题

# 664. 奇怪的打印机 (opens new window)

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

# 状态定义

dp[i][j] 表示打印区间[i,j]最少打印次数

# 初始状态

dp[i][i] = 1;

# 状态转移

  1. 若s[i] == s[j], 则在打印s[i]可以打印掉S[j] 即 dp[i][j] = dp[i][j-1]
  2. 若s[i] != s[j], 则拆分问题为 [i][k] 和[k+1][j] 两个问题，s[i][j] = min {[i][k],[k+1][j]} 其中k 属于[i,j)

# 结果

d[0][n-1]即为结果

为了保证动态规划的计算过程满足无后效性，在实际代码中，我们需要改变动态规划的计算顺序，从大到小地枚举 i，并从小到大地枚举 j，这样可以保证 当计算 f[i][j] 时，f[i][k] 和 f[k+1][j] 都已经被计算过。

public int strangePrinter(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][j - 1];
            } else {
                int min = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    min = Math.min(min, dp[i][k] + dp[k + 1][j]);
                }
                dp[i][j] = min;
            }
        }
    }
    
    return dp[0][n-1];
}

# 1000. 合并石头的最低成本 (opens new window)

# 1335. 工作计划的最低难度 (opens new window)

区间dp + 滚动数组+ 单调栈

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) {
            return -1;
        }
        int[] dp = new int[n];
        for (int j = 0, ma = 0; j < n; ++j) {
            ma = Math.max(ma, jobDifficulty[j]);
            dp[j] = ma;
        }
        for (int i = 1; i < d; ++i) {
            Deque<int[]> stack = new ArrayDeque<int[]>();
            int[] ndp = new int[n];
            for (int j = i; j < n; ++j) {
                int mi = dp[j - 1];
                while (!stack.isEmpty() && jobDifficulty[stack.peek()[0]] < jobDifficulty[j]) {
                    mi = Math.min(mi, stack.pop()[1]);
                }
                if (stack.isEmpty()) {
                    ndp[j] = mi + jobDifficulty[j];
                } else {
                    ndp[j] = Math.min(ndp[stack.peek()[0]], mi + jobDifficulty[j]);
                }
                stack.push(new int[]{j, mi});
            }
            dp = ndp;
        }
        return dp[n - 1];
    }
}
定义
性质
问题
664. 奇怪的打印机