【动态规划】区间DP

更新于 分类于 ， 阅读次数： 本文字数： 383 阅读时长 ≈ 1 分钟

区间DP是在区间上的动态规划

正文

  • 状态为区间：常设dp[i][j]表示区间 [i,j][i,j] 的状态
  • 思想：区间的状态由子区间更新而来
  • 题目技巧1：断环成链：首尾相连得到 22 倍环，转化为区间。注意区间要更新到 n+1∼2nn+1\sim 2n 的段。
1
2
3
4
5
6
7
8
for (int len = 1; len < n; len++) // 区间长度，由小区间开始dp，因为最先能确定的一定是最小的区间
    for (int l = 1, r = len + 1; l <= n && r <= n; l++, r++)
    {
        int ans = INF; // int ans=0; 取决于要求的是最大值还是最小值
        for (int k = l; k < r; k++)
            ans = max(ans, dp[l][k] + dp[k + 1][r] + 对这俩区间操作得到的结果);
        dp[l][r] = ans;
    }

题目