區(qū)間動態(tài)規(guī)劃（Interval DP）是一種用于解決某些需要處理區(qū)間或子段問題的動態(tài)規(guī)劃方法，特別適合于問題的解可以通過子區(qū)間的解進行組合的情況。該方法的核心思想是在子區(qū)間上進行分治，將大問題劃分為較小的子問題，通過解決這些子問題來構(gòu)建整個問題的解。

一、適用場景

區(qū)間 DP 主要用于解決一些涉及區(qū)間（或序列）的問題。這類問題通常要求在一個序列上做某種操作（如合并、拆分、重排等），并且這些操作的結(jié)果取決于其子區(qū)間的操作結(jié)果。常見的應(yīng)用包括：

1. 石子合并問題（合并區(qū)間）。
2. 括號匹配問題。
3. 最優(yōu)矩陣連乘問題。
4. 回文分割問題。

二、基本思路

區(qū)間 DP 的核心是通過枚舉區(qū)間的分割點，將問題分解為兩個或多個子區(qū)間的問題。解決每個子區(qū)間的問題后，再通過這些子區(qū)間的解組合得到整個區(qū)間的解。

步驟

1. 定義狀態(tài)：
   • 設(shè) dp[i][j] 表示在區(qū)間 [i, j] 上的最優(yōu)解。
2. 狀態(tài)轉(zhuǎn)移方程：
   • 根據(jù)問題的性質(zhì)，找到合適的分割方式，通常是選擇一個分割點 k，將區(qū)間 [i, j] 分為 [i, k] 和 [k+1, j] 兩個部分，并通過已知的子區(qū)間解來更新 dp[i][j]。
   • 一般形式的狀態(tài)轉(zhuǎn)移方程為：
     $$dp[i][j]=\underset{i\le k<j}{\min }(dp[i][k]+dp[k+1][j]+合并代價)$$
     其中 k 是區(qū)間的分割點，合并代價 由具體問題定義。
3. 初始狀態(tài)：
   • 最小區(qū)間的解（例如，當 i == j 時，區(qū)間僅包含一個元素，通?？梢灾苯拥玫阶顑?yōu)解）。
4. 結(jié)果：
   • 最終目標是通過填充 dp 數(shù)組，找到 dp[1][n]（即整個區(qū)間 [1, n] 的最優(yōu)解）。

時間復(fù)雜度：

區(qū)間 DP 的時間復(fù)雜度取決于問題的規(guī)模。對于每個區(qū)間 [i, j]，需要遍歷所有的分割點 k，這通常需要三層循環(huán)，因此復(fù)雜度為 $O(n^3)$，其中 n 是序列的長度。

三、例題

Acwing：282.石子合并

這是一個經(jīng)典的區(qū)間dp的問題。根據(jù)前面的描述，我們可以知道，區(qū)間dp實際上就是將整個區(qū)間問題轉(zhuǎn)化成多個區(qū)間子問題，然后狀態(tài)轉(zhuǎn)移至整個區(qū)間。

這里所說的石子合并，就是將兩個子區(qū)間合并成一個大區(qū)間。
我們將石子合并成一堆，那么在前一步一定是兩堆合并而來的，那么這兩堆分別又是一個子問題，實際上動態(tài)規(guī)劃也是處理子問題到整個問題轉(zhuǎn)移的算法。

我們可以定義$dp[i][j]$表示從初始開始編號為i + 1 ~ j + 1的石子合并成一堆的最小代價。那么必然有$dp[i][j]=dp[i][k]+dp[k+1][j]+m[j]?m[i?1]$（其中i<=k<=j）。

我們可以發(fā)現(xiàn)，動態(tài)規(guī)劃實際上就是帶有記憶的搜素。這里我們并不知道哪個子問題合并起來才是最優(yōu)的，因此我們遍歷所有可能得子區(qū)間劃分情況來求解。由這個遞推，我們從小區(qū)間到大區(qū)間依次求值。

注意合并才有代價，單個石子代價為0。
時間復(fù)雜度：$O(N^3)$

#include<bits/stdc++.h>
using  namespace  std;
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N; cin >> N;vector<int> m(N, 0);vector<vector<int>> dp(N, vector<int>(N, 0x3f3f3f3f));cin >> m[0]; dp[0][0] = 0;for(int i = 1; i < N; ++ i){cin >> m[i];m[i] += m[i - 1];dp[i][i] = 0;}for(int i = 1; i < N; ++ i){for(int j = 0; j + i < N; ++ j){int p = i + j;for(int k = j; k < p; ++ k){if(j != 0)dp[j][p] = min(dp[j][p], dp[j][k] + dp[k + 1][p] + m[p] - m[j - 1]);else dp[j][p] = min(dp[j][p], dp[j][k] + dp[k + 1][p] + m[p]);}}}cout << dp[0][N - 1];return 0;
}