算法提高课汇总

算法思路

理解题意

合并$N$堆石子, 每次合并相邻两堆, 合并的代价是这两堆石子质量之和. 求最小代价.

区间$DP$思路: 用状态表示一个区间.

$DP$分析

状态表示$dp(i, j)$

• 集合: 合并区间$i\sim j$内石子的所有合并方案.

• 属性: Min合并代价

状态计算

考虑合并完成的前一步: 将两个子区间$i\sim k$和$k + 1\sim j$合并. 我们可以以$k$作为集合划分依据.

考虑两个子区间对应集合:

• $i\sim k$: 合并区间$i\sim k$内石子的所有合并方案.

• $k + 1\sim j$: 合并区间$k + 1\sim j$内石子的所有合并方案.

为状态属性Min, 求上述两个集合对应最小值 — 根据我们的状态定义, 对应最小值分别为$dp(i, k)$与
$dp(k + 1, j)$.

所以$dp(i, j) = min\lbrace dp(i, k) + dp(k + 1, j)\rbrace + s(i, j)$. 其中$i\le k\lt j$, $s(i, j)$为合并两个子区间的代价: $i\sim j$所有石子的质量.

代码实现 $O(n^3)$

状态计算顺序

对于任意状态$dp(i, j)$, 状态的计算依赖于区间长度小于它的某些状态. 所以我们可以按区间长度由小到大
的顺序计算状态.

具体代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N]; //石子质量的前缀和
int dp[N][N];

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    memset(dp, 0x3f, sizeof dp);
    for( int i = 1; i <= n; i ++ )  dp[i][i] = 0; //合并一个石子的代价为0--已经合并完毕
    //实际上dp[i][0]/dp[0][j]也为0 不过我们在状态计算过程中不会用到它们

    for( int len = 2; len <= n; len ++ )
    {
        for( int i = 1; i + len - 1 <= n; i ++ )
        {
            int j = i + len - 1;
            for( int k = i; k < j; k ++ )
            {
                dp[i][j] = min( dp[i][j], dp[i][k] + dp[k + 1][j] );
            }
            dp[i][j] += s[j] - s[i - 1]; //最后加上合并整个区间的代价
        }
    }
    cout << dp[1][n] << endl;

    return 0;
}