旅游网站网页布局,花生壳建设网站,咨询公司ppt,wordpress chuxin石子合并问题是经典的区间dp问题#xff0c;我们需要枚举中间端点k的情况从而来推出dp数组的值。 文章目录 前言 一、石子合并问题 二、算法思路 1.问题思路 2.状态递推公式 二、代码如下 代码如下#xff08;示例#xff09;#xff1a; 2.读入数据 3.代码运行结果如下我们需要枚举中间端点k的情况从而来推出dp数组的值。 文章目录 前言 一、石子合并问题 二、算法思路 1.问题思路 2.状态递推公式 二、代码如下 代码如下示例 2.读入数据 3.代码运行结果如下 总结 前言
石子合并问题是经典的区间dp问题我们需要枚举中间端点k的情况从而来推出dp数组的值。 提示以下是本篇文章正文内容下面案例可供参考
一、石子合并问题
设有 N 堆石子排成一排其编号为 1,2,3,…,N。
每堆石子有一定的质量可以用一个整数来描述现在要将这 N堆石子合并成为一堆。
每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2 我们可以先合并 1、2 堆代价为 4得到 4 5 2 又合并 1、2 堆代价为 9得到 9 2再合并得到 11总代价为 491124
如果第二步是先合并 2、3堆则代价为 7得到 4 7最后一次合并代价为 11总代价为 471122。
问题是找出一种合理的方法使总的代价最小输出最小代价。
二、算法思路
1.问题思路
我们引入二维数组dpdp[i][j]表示的含义是从第i堆合并到第j堆所需要的最小代价数。 图1.1思路模拟 我们可以通过枚举区间长度len从1枚举n当然区间长度为1的时候说明只有一堆石子就不要合并代价为0。
然后我们在从1开始枚举左区间的起始端点ii的值从1枚举到n。我们知道区间长度len知道左端点i那么我们就可以得到区间的右端点jilen-1。
此时我们再枚举中间端点kk的值的话从i枚举到j-1因为我们最后用k将区间分成两堆分别是i到k堆和k1到j堆那么我们k的取值就是从i到j-1。
那么dp[i][j]的值就是从第i堆到第k堆的最小代价数加上第k1堆到第j堆的最小代价数再加上最后两堆的代价数我们通过观察可以发现最后两堆的合并一定是第i堆到k堆的连续合并和后面从第k1堆到第j堆的连续合并之和那么最后一次就相当于求区间和我们可以通过前缀和数组的方法来进行处理。
2.状态递推公式
当ij时即就一堆 当 枚举中间端点k时 注其中一维数组s表示石子质量的前缀和数组故求第i堆到第j堆石子重量的和为 dp数组构建代码如下 //区间长度for(int len 2; len n;len){//枚举左端端点for(int i 1; i len - 1 n;i){//最右端端点int j i len -1;//初始化dp[i][j] Integer.MAX_VALUE;mei//左右端点相等那么就一堆不需要进行操作if(i j){dp[i][j] 0;}//枚举中间端点for(int k i; k j-1;k){dp[i][j] Math.min(dp[i][j],dp[i][k]dp[k1][j]s[j]-s[i-1]);}}}
二、代码如下
代码如下示例
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;public class 石子合并 {static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static void main(String[] args) {Scanner sc new Scanner(new BufferedReader(new InputStreamReader(System.in)));int n sc.nextInt();int[] s new int[310];int[][] dp new int[310][310];for(int i 1; i n;i){s[i] sc.nextInt();}for(int i 1;i n;i){s[i] s[i]s[i-1];}//区间长度for(int len 2; len n;len){//枚举左端端点for(int i 1; i len - 1 n;i){//最右端端点int j i len -1;//初始化dp[i][j] Integer.MAX_VALUE;//左右端点相等那么就一堆不需要进行操作if(i j){dp[i][j] 0;}//枚举中间端点for(int k i; k j-1;k){dp[i][j] Math.min(dp[i][j],dp[i][k]dp[k1][j]s[j]-s[i-1]);}}}pw.println(dp[1][n]);pw.flush();}
}2.读入数据
代码如下示例
4
1 3 5 2
3.代码运行结果如下
22 总结
石子合并问题是经典的区间dp问题我们需要枚举中间端点k的情况从而来推出dp数组的值。
