class Solution {
public:// 思考:能否用滾動數組進行優化int minimumMoves(vector<int>& arr) {// 定義狀態dp[i][j]為i-j的最小步數int n = arr.size();vector<vector<int>> dp(n, vector<int>(n, 1e9 + 7));// 可以把這 1 次理解為一種 最小操作單位 或者// 基準操作次數后續計算更長的子數組的最小移動次數時// 都是基于這個基準進行遞推和比較的 如果將單個元素的情況定義為 0 次// 那么在后續的狀態轉移計算中// 可能會出現邏輯上的不順暢或者需要額外的特殊處理來區分這種情況// 反而會使算法變得復雜和難以理解for (int i = 0; i < n; ++i) {dp[i][i] = 1;}for (int i = 0; i + 1 < n; ++i) {if (arr[i] == arr[i + 1]) {dp[i][i + 1] = 1;} else {dp[i][i + 1] = 2;}}// 前面解決的是長度為2的子數組;// 現在解決的是長度為3及其以上的子數組的最小移動次數;for (int step = 3; step <= n; ++step) {// i+step-1表示索引的位置是從0位置到2及其以上的位置;for (int i = 0; i + step - 1 < n; ++i) {int j = i + step - 1;for (int k = i; k < j; ++k) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}if (arr[i] == arr[j]) {// 如果arr[i] == arr[j] 則dp[i][j] = min(dp[i][j] dp[i +// 1][j - 1]) 這是因為當子數組的首尾元素相同時// 可以考慮將首尾元素之外的子數組[i + 1, j -// 1]變為相同元素，然后首尾元素自然就相同了// 取這種情況下的最小移動次數與當前dp[i][j]的值比較// 取較小值更新dp[i][j]dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);}}}return dp[0][n - 1];}
};// 以下是這段代碼中狀態表示這樣定義的原因：
// 一、全面覆蓋問題的子問題空間
// 定義 dp[i][j] 表示將數組 arr 中從索引 i 到索引 j
// 的子數組變為相同元素所需的最小移動次數，這種二維的狀態表示能夠涵蓋數組的所有子數組情況。
// 從單個元素的子數組（i = j）到整個數組（i = 0，j = n - 1，其中 n
// 是數組長度），通過這種方式可以系統地考慮和處理每一種可能的子數組組合，確保不會遺漏任何一種情況，為求解整個問題提供了全面的基礎。
// 二、便于狀態轉移和遞推計算
// 在計算 dp[i][j]
// 的過程中，需要基于更短的子數組的狀態來推導。例如，通過枚舉分割點 k（i <= k <
// j），將 [i, j] 子數組分為 [i, k] 和 [k + 1, j] 兩部分，此時 dp[i][k] 和 dp[k
// + 1][j] 就是已經計算過的更短子數組的狀態。
// 這種二維狀態表示使得在進行狀態轉移時，可以很方便地根據子數組的分割關系來建立狀態之間的聯系，通過取
// dp[i][k] + dp[k + 1][j] 的最小值等方式來更新
// dp[i][j]，符合動態規劃中通過子問題的最優解來構建更大問題最優解的思想。
// 三、與問題的求解目標緊密相關
// 最終問題是求將整個數組變為相同元素的最小移動次數，而 dp[0][n - 1]
// 正好對應了這個最終目標。通過逐步計算從單個元素到整個數組的所有子數組的狀態，最終能夠得到
// dp[0][n - 1] 的值，即整個問題的解。
// 這種狀態表示方式直接針對問題的核心需求，將問題的求解過程轉化為對一系列子數組狀態的計算和更新，使得算法的設計和實現能夠緊密圍繞問題的本質，提高算法的針對性和有效性。// bool isPalindrome(const std::vector<int>& arr, int start, int end) {
//     while (start < end) {
//         if (arr[start] != arr[end]) {
//             return false;
//         }
//         start++;
//         end--;
//     }
//     return true;
// }// int minimumMoves(std::vector<int>& arr) {
//     int n = arr.size();
//     std::vector<int> dp(n, n);
//     dp[0] = 1;
//     for (int i = 1; i < n; ++i) {
//         dp[i] = dp[i - 1] + 1;
//         for (int j = 0; j < i; ++j) {
//             if (isPalindrome(arr, j, i)) {
//                 dp[i] = std::min(dp[i], (j > 0 ? dp[j - 1] : 0) + 1);
//             }
//         }
//     }
//     return dp[n - 1];