石子合并--区间DP_石子合并区间dp

一.什么是区间dp?

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

二.核心思路

既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点k，k分割点应该是从左端点，到右端点-1，因为分界点是将区间分成两堆，那另一堆肯定至少要有至少一个石子的。求解这段小区间在某个分割点下的最优解。

板子如下：

for(int len=2;len<=n;len++){//len表示从i到j的元素数量
    for(int i = 1; i+len-1<=n;i++){ // 循环条件是右端点小于等于n
        int l = i, r = i+len-1;
        dp[l][r]=(int)1e9;
        for(int k = l;k<r;k++){//k是两堆的分界点
            dp[l][r] = Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
        }
    }
}
1
2
3
4
5
6
7
8
9

三、石子合并问题

四、代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] sum = new int[305];
        int[][] dp = new int[305][305];
        for(int i = 1;i<=n;i++) {
            sum[i] = in.nextInt();
            sum[i] += sum[i-1];
        }
        for(int len=2;len<=n;len++) //len表示从i到j的元素数量
            for(int i = 1; i+len-1<=n;i++){ // 循环条件是右端点小于等于n
                int l = i, r = i+len-1;
                dp[l][r]=(int)1e9;
                for(int k = l;k<r;k++){//k是两堆的分界点
                    dp[l][r] = Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
                }
            }
        System.out.println(dp[1][n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22