[Acwing] 282. 石子合并 区间DP

前言

传送门 : https://www.acwing.com/problem/content/description/284/

感觉 和 线性dp差不多 只是考虑状态转移的 时候不一样了

(怎么不一样说不上来)

思路

要求 : 所有合并方案中 使得 答案最小的方案

状态表示 : f[i][j] 表示从第 i 堆 合并到 第 j 堆的 最小方案

(为什么呢？ 考感觉吧 QAQ)

状态转移 :

第 i 堆 合并到 第 j 堆 一定可以表示为

第 i 堆 先合并到 第 k堆 然后 第k+1堆 合并到 第 j堆 即 : f [ i ] [ j ] = f [ i ] [ k ] + f [ k + 1 ] [ j ] f[i][j]= f[i][k]+f[k+1][j] f[i][j]=f[i][k]+f[k+1][j]

因为每次合并 都有 值的相加 但是又不能改变原来的

所以我们还需要多处理一个 前缀和 数组

f [ i ] [ j ] = min ⁡ i ≤ k ≤ j − 1 f [ i ] [ k ] + f [ k + 1 ] [ j ] + s [ j ] − s [ i − 1 ] f[i][j]=\min _{i \leq k \leq j-1} f[i][k]+f[k+1][j]+s[j] - s[i-1] f[i][j]=mini≤k≤j−1​f[i][k]+f[k+1][j]+s[j]−s[i−1]

因此本题就好做了

(哈哈哈哈哈 好难啊)

CODE

/**
所有合并方式的 最小方案

方案是 (n-1)!

f[i][j]表示 将i到j合并成一堆的方案的集合 

状态计算
i>n;

    for(int i=1; i>a[i];
        s[i] +=s[i-1]+a[i];
    }


    for (int len = 1; len