前缀和动态规划

什么是前缀和?

给定长度n的序列array: a0、a1、a2、a3、……、an-1,给每一个前缀求一次和，S0=0,S1=a0,S2=a0+a1,……。这些前缀和维护一个长度为n+1数组S里，称为前缀和数组。

定义sum[k]为[0……k-1]的和，其中sum[0]表示数组中没有数字被选中，sum[1]表示只选中第一个数nums[0]。预先计算0-k(0<=k<=n-1)的和，这一系列的和都是从0开始的，因此称为前缀和。公式如下:

1. k=0 时:sum(0,0)=0
2. 1<=k<=n-i 时: sum(0,k)=nums[0]+nums[1]+……+nums[k-1]

通过前缀和，我们可以解决以下场景:

• 计算区间sum[i,j]的和: sum[i,j]=sum[0,j+1]-sum[0,i]

前缀和中的动态规划

前缀和中的动态规划思想，如下:

1. 状态定义: sum[i]表示nums[0]-nums[i-1]的和
2. 状态转移方程: sum[i]=sum[i-1]+nums[i-1];
3. 初始化: sum[0]=0

扩展

在有些问题中，计算答案时同时需要用到前缀和（积）和后缀和（积）