石子合并系列问题

这篇具有很好参考价值的文章主要介绍了石子合并系列问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

石子合并

石子合并问题在网上有三个版本:

  • AcWing 282. 石子合并
    设有 N 堆石子排成一排,其编号为 1,2,3,…,N。

    每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。

    每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。
    找出一种合理的方法,使总的代价最小,输出最小代价。

  • LibreOJ #10147. 「一本通 5.1 例 1」石子合并 / 洛谷 P1880 [NOI1995] 石子合并

    N 堆石子绕圆形操场摆放,现要将石子有次序地合并成一堆,规定每次只能选相邻的 2 堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分。

    试设计出一个算法,计算出将 N 堆石子合并成1堆的最小得分和最大得分。

  • LeetCode 1000. 合并石头的最低成本
    N 堆石头排成一排,第 i 堆中有 stones[i] 块石头。

    每次*移动(move)*需要将连续的 K 堆石头合并为一堆,而这个移动的成本为这 K 堆石头的总数。

    找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1

为了方便讲述和理解,可以将上述三题总结为一题的三个小问进行表达:

N N N 堆石子排成一排,其编号为 1 ,   2 ,   3 ,   …   ,   N 1,\ 2,\ 3,\ …\ ,\ N 1, 2, 3,  , N
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N N N 堆石子合并成为 1 1 1 堆。
每次只能合并相邻的 2 2 2 堆,合并的代价为这 2 2 2 堆石子数量之和,合并后的相对位置不变。

  1. 试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分。
  2. 将这 N N N 堆石子在圆形操场摆放,即首尾堆相连(第 1 1 1 堆和第 N N N 堆),请问此时的最小得分为多少?
  3. 若一次可合并 K K K 堆,找出把所有石头合并成 1 1 1 堆的最低成本。如果不可能,返回 − 1 -1 1

输入格式
数据的第 1 1 1 行是正整数 N N N,表示有 N N N 堆石子。
2 2 2 行有 N N N 个整数,第 i i i 个整数表示第 i i i 堆石子的个数。

思路分享

一个错误的思路:局部最优解

一开始看到这题很容易联想到曾经学过的哈夫曼编码思路(多加个相邻的约束条件),我也尝试过编写该代码,发现不讨巧的情况下只能通过 6 / 10 6/10 6/10 的测试样例。因为它是一种贪心算法,只考虑到了当前情况下的最优解,下面我会给出样例进行解释。

你应该注意到上面第二小问删去了最大得分的部分,这是因为它的动归写法和最小得分思路一样,但为了更清晰的否定掉“哈夫曼编码”在此题的思路,我需要引用一个最大得分的反例:

石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

可以从下图看到第一次合并有两种组合,分别为左侧的 6, 12 和右侧的 3, 15,如果我们按照贪心算法,去选择第一次遇到的最大组合,会发现得到的最大值为 158,而实际上正确答案为右侧的 171

石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

当然你选最后一次的最大组合是一样的,只需要将当前输入的序列逆置一下就能发现错误(碎碎念:可以用这个方法来通过LibreOJ上 7 / 10 7/10 7/10 的测试样例)。

第一问(排成一排)-- 动态规划

利用 dp 数组 存储最小的合并代价:第 i i i 个石堆 j j j 个石堆的最小合并代价为 d p [ i ] [ j ] dp[i][j] dp[i][j]
只有一个石堆时,最小合并代价为0,设 d p [ i ] [ i ] = 0 , i = 1.. N dp[i][i] = 0, i = 1..N dp[i][i]=0,i=1..N
注意,为了表达方便:这里第 i i i 堆石子对应的下标就是 i i i 而非 i − 1 i-1 i1

石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

想一下最简单的合并情况:相邻两个石堆 i i i 和石堆 i + 1 i + 1 i+1 ,它们合并代价是两个石堆石子数的总和,即
d p [ i ] [ i + 1 ] = s t o n e s [ i ] + s t o n e s [ i + 1 ] (1) dp[i][i+1] = stones[i] + stones[i+1] \tag{1} dp[i][i+1]=stones[i]+stones[i+1](1)
那么非相邻的两个石堆之间的合并代价又是什么呢?

因为每次只能合并相邻的两堆,石堆 i i i 想与石堆 j j j 合并成一堆前,必然要经过相邻两个石堆的合并,也就是说存在石堆 k k k 将石堆 ( i . . . j ) (i...j) (i...j) 划分为 ( i . . . k ) (i...k) (i...k) ( k + 1... j ) (k+1...j) (k+1...j) ,这两个石堆的合并代价分别为 d p [ i ] [ k ] dp[i][k] dp[i][k] d p [ k + 1 ] [ j ] dp[k+1][j] dp[k+1][j]

回顾下 dp 数组 的定义:存储最小的合并代价(指的是合并的总代价,总代价 = 每次石子合并的代价之和)。

故有
石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

而两石堆的石子数之和是显然的,这里给出最后的公式:
石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

其实这是一个区间动态规划问题:

  • “排成一排的 N N N 堆石子” => N N N 个连续的小区间。

  • 相邻的才可以合并,合并的固定代价为两石堆的石子数之和 s t o n e s [ i ] + s t o n e s [ i + 1 ] stones[i] + stones[i+1] stones[i]+stones[i+1]” => 计算区间的前缀和进行表示(你可以将前缀和理解为当前石堆及之前石堆石子的总数量):
    s [ 0 ] = 0 s [ i ] = s [ i − 1 ] + s t o n e s [ i ] s t o n e s [ i ] + s t o n e s [ i + 1 ] = s [ i + 1 ] − s [ i − 1 ] ⇓ s t o n e s [ i ] + . . . + s t o n e s [ k ] + s t o n e s [ k + 1 ] + . . . + s t o n e s [ j ] = s [ j ] − s [ i − 1 ] (4) s[0] = 0\\ s[i] = s[i-1] + stones[i]\\ stones[i] + stones[i+1] = s[i+1] - s[i-1]\\ \Downarrow\\ stones[i]+...+stones[k]+ stones[k+1]+...+stones[j] = s[j] - s[i-1] \tag{4} s[0]=0s[i]=s[i1]+stones[i]stones[i]+stones[i+1]=s[i+1]s[i1]stones[i]+...+stones[k]+stones[k+1]+...+stones[j]=s[j]s[i1](4)
    所以进一步的,可以将式(3)写为:石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

( i , k ) (i, k) (i,k) 和$ (k+1, j)$ 本身可以再划分成两小堆,因此 ( 5 ) (5) (5) 式其实是就是我们代码的核心。

你可能发现了上面的式子中 k k k 的取值范围为 i . . j − 1 i..j-1 i..j1,这是为了让 ( 5 ) (5) (5) 式也能够计算相邻两个石堆合并的代价( d p [ i ] [ i ] = 0 dp[i][i] = 0 dp[i][i]=0,所以当 j = i + 1 j = i+1 j=i+1 时, ( 5 ) (5) (5) 式等于 ( 1 ) (1) (1) 式)。

现在可以来编写代码来完成这题。

代码

Python

# 处理输入(只有LeetCode不需要处理)
N = int(input())
stones = [0] + list(map(int, input().split()))
len = N + 1

# 计算前缀和
s = [0] * len
for i in range(1, len):
    s[i] = s[i - 1] + stones[i]
    
# dp数组初始化
dp = [[0] * (len) for _ in range(len)]

# 用d(i, j)表示s[j] - s[i - 1]
d = lambda i, j: s[j] - s[i - 1]

# 计算dp,length从2开始,因为区间长度(石头堆数)至少为2时才能合并
for length in range(2, N + 1):
    i = 1
    while (i + length - 1 <= len - 1):
        j = i + length - 1
        dp[i][j] = float("inf")
        for k in range(i, j):	# k的取值范围是 i 到 j-1
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i, j)) # 代码等价写法在下面
        i += 1
print(dp[1][N])

C

#include <limits.h> // INT_MAX
#include <stdio.h> // scanf, printf
#include <stdlib.h> // malloc
#include <string.h> // memset

#define d(i, j) (s[j]-s[i-1]) // 用d(i, j)表示s[j] - s[i - 1]
#define min(x, y) ((x)<(y)?(x):(y))

int main(){
    // 处理输入
    int N, *stones, len;
    scanf("%d", &N);
    len = N + 1;
    stones = (int *)malloc(sizeof(int) * len);
    for (int i = 1; i <= N; i++){
        scanf("%d", &stones[i]);
    }
    // 计算前缀和
    int *s = (int *)malloc(sizeof(int) * len);
    memset(s, 0, sizeof(int) * len);
    for (int i = 1; i < len; i++)
        s[i] = s[i - 1] + stones[i];

    // dp数组初始化
    int **dp = (int **)malloc(sizeof(int *) * len);
    for (int i = 0; i < len; i++){
        dp[i] = (int *)malloc(sizeof(int) * len);
        memset(dp[i], 0, sizeof(int) * len);
    }
    
    // 计算dp
    int length, i, j, k;
    // length从2开始,因为区间长度(石头堆数)至少为2时才能合并
    for (length = 2; length <= N; length++){
        i = 1;
        for (j = i + length - 1; j <= len - 1; j++){
            dp[i][j] = INT_MAX;
            for (k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j)); // 代码等价写法在下面
            i += 1;
        }
    }
    printf("%d", dp[1][N]);
    return 0;
}

d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + d ( i , j ) ) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j)) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+d(i,j))等价于下面的代码

int tmp = dp[i][j];
dp[i][j] = dp[i][k] + dp[k + 1][j] + d(i,j);
if (tmp < dp[i][j])
    dp[i][j] = tmp;

第二问(排成一圈)

第二问较第一问的区别是石子在圆形操场排成一圈,也就是说现在 d p [ 1 ] [ N ] dp[1][N] dp[1][N] 不一定是合并的最小代价。

以下面的输入为例进行解释。

下图为排列状况,排成一圈相当于 4 4 4 1 1 1 的路径通了,原来的数组变成了循环数组,乍一看好像很复杂,但实际上可以将其化简成右下角非循环的格式: 1   2   3   4   1   2   3 1\ 2\ 3\ 4\ 1\ 2\ 3 1 2 3 4 1 2 3

石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法

希望你有注意到数组上方圆圈内标注的 ① ② ③ ④,此时 ① 所代表的 d p [ 1 ] [ 4 ] dp[1][4] dp[1][4] 将不一定是合成的最小代价,需要在最后的输出前对比这四个小区间各自的最小合成代价( d p [ i ] [ i + N − 1 ] , i = 1.. N , N = 4 dp[i][i+N-1], i = 1..N, N = 4 dp[i][i+N1],i=1..N,N=4),来找到真正的最小值,也就是:
石子合并问题,算法,leecode数据结构练习,石子合并,动态规划,算法
到这步,其实已经完成了第一问到第二问代码的转换:

Python

N = int(input())
- stones = [0] + list(map(int, input().split()))
+ stones = [0] + (list(map(int, input().split())) * 2)[:-1]
- len = N + 1
+ len = N + N

# 前缀和
s = [0] * len
for i in range(1, len):
    s[i] = s[i - 1] + stones[i]

dpMax = [[0] * (len) for _ in range(len)]
dpMin = [[0] * (len) for _ in range(len)]

d = lambda i, j: s[j] - s[i - 1]
for length in range(2, N + 1):
    i = 1
    while (i + length - 1 <= len - 1):
        j = i + length - 1
        dpMin[i][j] = float("inf")
        for k in range(i, j):
            dpMin[i][j] = min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j] + d(i, j))
        i += 1

- print(dp[1][N])
+ minl = float("inf")
+ for i in range(1, N + 1):
+	minl = min(minl, dpMin[i][i + N - 1])
+ print(minl)

C

#include <limits.h> // INT_MAX
#include <stdio.h> // scanf, printf
#include <stdlib.h> // malloc
#include <string.h> // memset

#define d(i, j) (s[j]-s[i-1]) // 用d(i, j)表示s[j] - s[i - 1]
#define min(x, y) ((x)<(y)?(x):(y))

int main(){
    // 处理输入
    int N, *stones, len;
    scanf("%d", &N);
-   len = N + 1;
+	len = N + N + 1;

    stones = (int *)malloc(sizeof(int) * len);
    for (int i = 1; i <= N; i++){
        scanf("%d", &stones[i]);
+       stones[i + N] = stones[i];
    }

    // 计算前缀和
    int *s = (int *)malloc(sizeof(int) * len);
    memset(s, 0, sizeof(int) * len);
    for (int i = 1; i < len; i++)
        s[i] = s[i - 1] + stones[i];

    // dp数组初始化
    int **dp = (int **)malloc(sizeof(int *) * len);
    for (int i = 0; i < len; i++){
        dp[i] = (int *)malloc(sizeof(int) * len);
        memset(dp[i], 0, sizeof(int) * len);
    }
    
    // 计算dp
    int length, i, j, k;
    // length从2开始,因为区间长度(石头堆数)至少为2时才能合并
    for (length = 2; length <= N; length++){
        i = 1;
        for (j = i + length - 1; j <= len - 1; j++){
            dp[i][j] = INT_MAX;
            for (k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j)); 
            i += 1;
        }
    }
+   int minl = INT_MAX;
+ 	for (i = 1; i <= N; i++)
+    	minl = min(minl, dpMin[i][i + N - 1]);

-   printf("%d", dp[1][N]);
+   printf("%d\n", minl);
	return 0;
}

第三问(每次合成 K 堆)

每次合成 K K K 堆意味着每次合并后,总堆数减少 K − 1 K-1 K1 堆。最后需要合并到 1 1 1 堆,所以石堆数量 N N N 需要满足
N = Z ∗ ( K − 1 ) + 1 ⇓ 0 = = ( N − 1 )   %   ( K − 1 ) (1) N = Z * (K - 1) + 1\\ \Downarrow\\ 0 == (N-1)\ \%\ (K - 1) \tag{1} N=Z(K1)+10==(N1) % (K1)(1)
才能合并,所以我们有了第一个条件判断:if (0 != (N - 1) % (K - 1)): 返回 -1

注意,不能仅使用看起来等价的 1 = = N   %   ( K − 1 ) 1 == N\ \%\ (K-1) 1==N % (K1) ,因为当 K = 2 K=2 K=2 时,任意数量的石堆均能合并成 1 1 1 堆,而此时 0 = = N   %   ( K − 1 ) 0 ==N\ \%\ (K-1) 0==N % (K1)

第三问中,dp数组 同样表示最小合成代价,但这个最小合成代价的指的是合并到不能合并为止时到最小代价,也就是说:当 N > K N > K N>K 时,即使 N N N 不满足最后合成到 1 1 1 堆的条件, d p [ 1 ] [ N ] dp[1][N] dp[1][N] 也不为 0 0 0。当然,还需要注意到的是:在最开始的条件判断中,无法合并为 1 1 1 堆的石堆已经被筛除了,我们现在这样设计的目的是为了方便求得 d p [ 1 ] [ N ] dp[1][N] dp[1][N],其中 0 = = ( N − 1 )   %   ( K − 1 ) 0 == (N-1)\ \%\ (K - 1) 0==(N1) % (K1)

N = 5 N = 5 N=5,来看看 dp数组 的取值。

  • d p [ 1 ] [ 3 ] = d ( 1 , 3 ) dp[1][3] = d(1,3) dp[1][3]=d(1,3)
  • d p [ 2 ] [ 4 ] = d ( 2 , 4 ) dp[2][4] = d(2,4) dp[2][4]=d(2,4)
  • d p [ 3 ] [ 5 ] = d ( 3 , 5 ) dp[3][5] = d(3,5) dp[3][5]=d(3,5)
  • d p [ 1 ] [ 4 ] = m i n ( d p [ 1 ] [ 3 ] , d p [ 2 ] [ 4 ] ) dp[1][4] = min(dp[1][3], dp[2][4]) dp[1][4]=min(dp[1][3],dp[2][4])
  • d p [ 2 ] [ 5 ] = m i n ( d p [ 2 ] [ 4 ] , d p [ 3 ] [ 5 ] ) dp[2][5] = min(dp[2][4], dp[3][5]) dp[2][5]=min(dp[2][4],dp[3][5])
  • d p [ 1 ] [ 5 ] = m i n ( d p [ 1 ] [ 4 ] , d p [ 2 ] [ 5 ] ) + d ( 1 , 5 ) = m i n ( d p [ 1 ] [ 3 ] , d p [ 2 ] [ 4 ] , d p [ 3 , 5 ] ) + d ( 1 , 5 ) dp[1][5] = min(dp[1][4], dp[2][5]) + d(1,5) = min(dp[1][3], dp[2][4], dp[3,5]) + d(1,5) dp[1][5]=min(dp[1][4],dp[2][5])+d(1,5)=min(dp[1][3],dp[2][4],dp[3,5])+d(1,5)

0 = = ( j − i ) % ( K − 1 ) 0 == (j - i) \% (K - 1) 0==(ji)%(K1) 时, i . . j i..j i..j 堆石堆可以合并成一堆,此时 d p [ i ] [ j ] dp[i][j] dp[i][j] 需要计算最后一次合并的代价 d ( i , j ) d(i,j) d(i,j)
0    ! = ( j − i ) % ( K − 1 ) 0\ \ != (j - i) \% (K - 1) 0  !=(ji)%(K1) 时, i . . j i..j i..j 堆石堆不能合并成一堆,此时 d p [ i ] [ j ] dp[i][j] dp[i][j] 等于合成到 < K <K <K 堆时的最小合成代价。

总结其中规律,有:
d p [ i ] [ j ] = { min ⁡ k ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] ) + d ( i , j ) , 0 = = ( j − i ) % ( K − 1 ) min ⁡ k ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] ) , 0    ! = ( j − i ) % ( K − 1 ) 其 中 k = i ,   k < j ,   k ← k + K − 1 (2) dp[i][j]= \begin{cases} \min_k(dp[i][k]+dp[k+1][j])+d(i,j),&& 0 == (j - i) \% (K - 1)\\ \min_k(dp[i][k]+dp[k+1][j]), && 0\ \ != (j - i) \% (K - 1)\\ \end{cases} \\其中 k=i,\ k<j,\ k \leftarrow k+K-1 \tag{2} dp[i][j]={mink(dp[i][k]+dp[k+1][j])+d(i,j),mink(dp[i][k]+dp[k+1][j]),0==(ji)%(K1)0  !=(ji)%(K1)k=i, k<j, kk+K1(2)文章来源地址https://www.toymoban.com/news/detail-781895.html

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define d(i, j) (s[j]-s[i-1])
#define min(x, y) ((x)<(y)?(x):(y))

int mergeStones(int* stones, int N, int K){
    int len, *nums;
    // 每次合并减少k-1个石堆,最后需要剩一个
    if (0 != (N - 1) % (K - 1)) // 等价于 K != 2 && 1 != stonesSize % (K - 1))
        return -1;
    len = N + 1;
    
    // 计算前缀和
    int *s = (int *)malloc(sizeof(int) * len);
    memset(s, 0, sizeof(int) * len);
    for (int i = 1; i < len; i++)
        s[i] = stones[i - 1] + s[i - 1];

    // dp数组初始化
    int **dpMin = (int **)malloc(sizeof(int *) * len);
    for (int i = 0; i < len; i++){
        dpMin[i] = (int *)malloc(sizeof(int *) * len);
        memset(dpMin[i], 0, sizeof(int) * len);
    }

    int length, i, j, k;
    // length从K开始,因为合并时区间长度至少为K
    for (length = K; length <= N; length++){
        i = 1;
        for (j = i + length - 1; j <= len - 1; j++){
            dpMin[i][j] = INT_MAX;
            for (k = i; k < j; k += K-1){
                dpMin[i][j] = min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j]);
            }
            if (0 == (length - 1) % (K - 1)) // 式(2)
                dpMin[i][j] += d(i, j);
            i += 1;
        }
    }

    return dpMin[1][N];
}

到了这里,关于石子合并系列问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leecode56:合并区间(贪心算法)

    第一眼看到这个题目觉得应该是比较第一个值的大小,因为如果第n个值比n-1个值的右边还小于等于,那么说明区间可以连起来。但是不会写比较强!! Arrays.sort()函数里, Arrays.sort(shuzu, Comparatorint[](){ }); 千万记得排序后分清楚哪个是原本的哪个是当前的!!以及新加一个

    2024年02月07日
    浏览(46)
  • 【数据结构与算法】 合并排序

    CSDN话题挑战赛第1期 活动详情地址:https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f 参赛话题:Java学习记录 话题描述:可以记录一下平时学习Java中的一些知识点、心得、例题、常见的问题解决 好文推荐🔥图文并茂详解十大排序算法让您回味无穷 合并排序是建立在归并操作

    2024年02月02日
    浏览(38)
  • 数据结构:两个顺序表合并算法

            将a,b两个有序顺序表进行合并,放在c顺序表当中,并且要保证顺序表c仍然有序。         因为a,b两个顺序表是有序的,所有可以从前往后一起查找a,b当中最小的一个数值,放入到c中。         如果遍历到最后,a遍历完了,b没有遍历完,就把b剩下的放入

    2024年02月08日
    浏览(37)
  • 石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

    一、石子合并 (经典例题) 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合

    2024年02月19日
    浏览(44)
  • 【每日算法 && 数据结构(C++)】—— 03 | 合并两个有序数组(解题思路、流程图、代码片段)

    An inch of time is an inch of gold, but you can’t buy that inch of time with an inch of gold. An inch of time is an inch of gold, but you can\\\'t buy that inch of time with an inch of gold 给你两个有序数组,请将两个数组进行合并,并且合并后的数组也必须有序 这个题目要求将两个有序数组合并成一个有序数组。在数

    2024年02月11日
    浏览(53)
  • 合并石子(动态规划)

    首先理解题意,笔者看到这道题时首先想到的是贪心,仔细分析后发现题上没说石子根据一定顺序来摆放,易证局部最优解不一定是问题最优解,没有贪心性质,不能用贪心 然后需要强调的是,该题是一个圆形结构 这里为了方便理解,我们先将其简化为线性结构 先看一个简

    2024年02月01日
    浏览(35)
  • 石子合并(区间dp)

    (1)f[l][r]表示l~r之间合并的最小代价。 (2)将l~r拆成l~k,k+1~r两份分别最优合并,再把两份合并,对于每个l,r通过枚举所有可能k探寻最优。 (3)最终目标是f[1][n],注意到长区间是由短区间递推出来的,所以由小到大枚举区间长度,再枚举起点,此时l = 起点,r = 起点 +len

    2024年02月10日
    浏览(32)
  • 动态规划——区间dp [石子合并]

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月12日
    浏览(45)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(58)
  • 石子合并(动态规划 区间DP)+详细注释

    原题链接   活动 - AcWing 题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包