【2】python算法练习--动态规划专题（1）

区间dp模板题：合并石子

拿到这道题，根据题目所说，需要我们寻找最小合并的数值，很容易就联想到dp，去寻找子问题，化整为零。因为如果直接暴力的话，就是N的阶乘的时间复杂度，肯定没有办法在规定时间内解决问题。那我们就想：怎么样才会是最小值呢，在分析最小子问题之前，我们要明白一点就是：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并。有了这个思路，就很好的可以分解成一个一个小的子问题了，也就是从最小的两个石子开始，相互比较寻找最小值到最后连续的两部分就可以进行最后的运算。

n=int(input())
s=[0]*(n+1)#初始化前缀和
t=list(map(int,input().split()))
for i in range(1,n+1):
   s[i]=s[i-1]+t[i-1]#此处t[i-1]是因为索引下标从0开始 前缀和计算完成
'''
现在进行初始化dp数组
'''
dp=[[0]*(n+1)for _ in range(n+1)]# 下划线 为占位符
'''
开始区间dp了
'''
#设置区间 从最小的2开始 1时无意义
for len in range(2,n+1):
   l=1#设定边界 由左边界确定右界
   while(l + len - 1<=n):
      r = l + len - 1
      dp[l][r] = float("inf")#由于接下来要进行取最小值，因此把内部的值置为无穷大inf
      for k in range(l,r):
         dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1])
      l +=1
print(dp[1][n])

 s[r]-s[l-1]就是前缀和代表合并最后两段需要得代价。