?https://codeforces.com/problemset/problem/1312/E

題意：

給定n個(gè)數(shù)，每次選兩個(gè)相等且相鄰的數(shù)a[i]=a[i+1]合并變成a[i]，求數(shù)列最小長(zhǎng)度

思路：

動(dòng)態(tài)規(guī)劃使用兩個(gè)數(shù)組

用dp[i][j]表示將區(qū)間 [i,j]壓縮后的長(zhǎng)度, 區(qū)間[i,j]的初始dp值為0X7F7F7F7F

用num[i][j]表示將區(qū)間 [i,j]壓縮成一個(gè)數(shù)字后的數(shù)字, 區(qū)間[i,j]的初始值為0

狀態(tài)轉(zhuǎn)移方程：

①(dp[l][k] == 1 && dp[k+1][r] == 1 && num[l][k] == num[k+1][r]) dp[l][r] = 1, num[l][r] = num[l][k] + 1;

①的情況不需要執(zhí)行②，因?yàn)閐p[l][r]=1;已經(jīng)最小，

②dp[l][r] = min(dp[l][r],dp[l][k_1 ] + dp[k_1+1][r] );