區間DP

定義

區間動態規劃（Interval Dynamic Programming），簡稱區間DP，是動態規劃領域的一個重要分支，專門用于解決涉及區間問題的最優化問題。這類問題通常需要在給定的一組區間上找到最優解，比如求解最長上升子序列、最優三角剖分、區間覆蓋問題等。

基本概念

1. 區間定義：問題中涉及到的區間通常由兩個端點（起點和終點）定義，如[i, j]表示一個閉區間。
2. 狀態表示：區間DP的核心在于狀態的定義，狀態通常由區間長度和區間位置來描述，例如dp[i][j]可以表示區間[i, j]上的最優解。
3. 狀態轉移：區間DP的狀態轉移是從較小區間的信息推導出較大區間的信息。通常通過枚舉區間長度或枚舉區間斷點來進行狀態轉移。
4. 決策過程：在區間DP中，一個狀態的值可能由多個子區間狀態經過某種計算（如最大值、最小值、和等）得到，這是通過決策過程來確定的。

運用情況

通常用于具有區間合并、分割等特征的問題。比如計算一段區間的最優值（如最大和、最小和等），或者判斷區間內的某種狀態。一些常見的應用場景包括計算字符串的編輯距離、計算區間內的最大連續子段和等。

注意事項

• 正確定義狀態，清晰表示出區間的特征和所需的信息。
• 仔細考慮區間的劃分和合并方式，確保覆蓋所有情況且不重復計算。
• 注意邊界條件的處理。

解題思路

• 確定區間的表示方式，通常用左右端點來表示一個區間。
• 設計狀態表示，比如用 dp[i][j] 表示區間[i,j]的某種最優值或狀態。
• 寫出狀態轉移方程，根據問題的具體要求，確定如何從較小的區間的狀態推導出較大區間的狀態。
• 按照合適的順序進行計算，通常是從小到大逐步計算出各個區間的狀態。

例如，計算一個數列在某區間內的最大連續子段和問題。可以定義 dp[i][j] 為區間[i,j]內的最大連續子段和，然后通過考慮區間的分割情況來推導出狀態轉移方程。

解題步驟

1. 定義狀態：明確dp數組的含義，比如dp[i][j]表示什么。
2. 初始化：確定dp數組的起始值，通常是當區間長度為1或2時的初始情況。
3. 狀態轉移方程：根據問題特性，推導出如何從較小的子區間狀態計算出較大區間狀態的公式。
4. 遍歷順序：通常按照區間長度從小到大，然后是區間起始點的順序進行遍歷，確保計算每個狀態時，其依賴的所有子狀態已經計算完畢。
5. 求解目標：根據問題的具體要求，從dp數組中提取出最終答案。

實例應用

• 最長公共子序列（LCS）問題：可以轉化為區間DP問題，求解兩個序列的最長公共子序列長度。
• 最優三角剖分：在平面上有n個點，每個點的坐標為(xi, yi)，找到一個三角剖分，使得所有三角形的面積之和最大。
• 區間覆蓋問題：給定一系列區間，找到最少數量的區間，使得它們覆蓋整個數軸。

區間DP的難點在于正確定義狀態和設計高效的狀態轉移方程，以及理解區間如何相互作用以達到全局最優解。掌握區間DP的關鍵在于多練習，理解典型問題的解決方案，并能夠抽象出問題的共通模式。

AcWing 320. 能量項鏈

題目描述

320. 能量項鏈 - AcWing題庫

運行代碼

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][N];
int main()
{cin >> n;for (int i = 1; i <= n; i ++ ){cin >> w[i];w[i + n] = w[i];}for (int len = 2; len <= n + 1; len ++ )for (int l = 1; l + len - 1 <= n * 2; l ++ ){int r = l + len - 1;for (int k = l + 1; k < r; k ++ )f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);}int res = 0;for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]);cout << res << endl;return 0;
}

代碼思路

• 首先定義了一些常量和數組，N?表示最大可能的珠子數量，INF?是一個很大的常數表示無窮大，w?數組用于存儲珠子的標記值，f?數組用于存儲不同區間聚合的最大能量。
• 輸入珠子的數量?n?后，將珠子的標記值讀入，并進行了一個循環處理，將原序列重復一遍，這樣便于處理環形的情況。
• 然后通過三重循環來計算動態規劃數組?f。最外層循環表示區間長度，從 2 開始遞增到?n+1。對于每個確定長度的區間，通過內層的兩個循環確定左右端點?l?和?r，再通過中間的?k?遍歷所有可能的分割點，計算當前區間在不同分割情況下的最大能量，并更新?f[l][r]。
• 最后通過一個循環找到所有長度為?n?的區間（對應原環形序列的一圈）中的最大能量值并輸出。

總的來說，這段代碼通過動態規劃的方法逐步計算出所有區間的最優聚合能量，最終得到整個序列的最大能量。

改進思路

1. 可以考慮添加一些注釋提高代碼的可讀性。
2. 對于一些重復計算的部分，可以進一步優化計算邏輯，避免不必要的重復計算。

改進代碼

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][N];
int main()
{cin >> n;for (int i = 1; i <= n; i ++ ){cin >> w[i];w[i + n] = w[i]; // 將序列重復，處理環形情況}for (int len = 2; len <= n + 1; len ++ )for (int l = 1; l + len - 1 <= n * 2; l ++ ){int r = l + len - 1;for (int k = l + 1; k < r; k ++ ){// 計算并更新最大能量f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);}}int res = 0;for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]); // 找到環形一圈的最大能量cout << res << endl;return 0;
}