C语言中如何实现合并石子问题的动态规划算法？

本文共计3118个文字，预计阅读时间需要13分钟。

1. 前言+区间类型问题，指求一个数列中某一段区间的值，包括求和、最大值等简单或复杂问题。此类问题也适用于动态规划思想。例如，前缀和就是最简单的区间问题。例如，给定如下数组：+i“

1. 前言

区间类型问题，指求一个数列中某一段区间的值，包括求和、最值等简单或复杂问题。此类问题也适用于动态规划思想。

如前缀和就是极简单的区间问题。如有如下数组：

int nums[]={3,1,7,9,12,78,32,5,10,11,21,32,45,22}

现给定区间信息[3,6]，求区间内所有数字相加结果。即求如下图位置数字之和。

Tips： 区间至少包括 2 个属性，起始端和结束端，求和范围包含左端和右端数字。

直接的解法：

• 累加数组中 0~6区间的值s1。
• 累加数组中0~2区间的值s2。
• 将 s1中的值减去s2中的值。得到最终结果。

如果对任意区间的求解要求较频繁，会存在大量的重复计算。