这个系列主要谈一谈关于DP的优化，所有题目均为平时刷题所遇到的，如果涉及到DP优化相关的技巧我就会在这里记录下来。今天这个题目讲的是通过改变DP顺序来进行优化的一种方法。

合唱

时间限制：2秒
空间限制：131072K

描述

小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。
对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。
现在要对把这n个音调分配给小Q或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。
如样例所示: 小Q选择演唱{5, 6}难度为1, 牛博士选择演唱{1, 2, 1}难度为2,难度之和为3,这一个是最小难度和的方案了。

输入

输入包括两行,第一行一个正整数n(1 ≤ n ≤ 2000) 第二行n个整数v[i](1 ≤ v[i] ≤ 10^6), 表示每个音调。

输出

输出一个整数,表示小Q和牛博士演唱最小的难度和是多少。

样例输入

5
1 5 6 2 1

样例输出

3

分析

由于每个音要么由牛博士演唱，要么由小Q演唱，所以总的方案数有2^N次方种可能，无法直接枚举。容易发现枚举过程中存在大量重复计算，因此考虑使用动态规划求解。

不妨设f[i][j]（其中i>j）代表两人演唱的最后一个音分别为i和j时，最小的难度和。同时，我们假设s[i][j]代表连续演唱i~j所有的音所产生的难度和，这个s[i][j]可以事先预处理得到。

那么可以得到:

这个方程最麻烦的地方在于需要枚举这个k，如果每次求f[i][j]都去枚举k的话，复杂度就退化成了N^3 。首先看一个N^3的代码：

void dp()
{
    int i,j,k;
    memset(f,0x3f,sizeof(f));
    mem(s);
    f[0][0]=0;
    for(i=2;i<=n;i++) s[i]=s[i-1]+abs(a[i]-a[i-1]);
    for(i=1;i<=n;i++)
    {
        f[i][0]=s[i];
        for(j=1;j<i;j++)
            for(k=0;k<j;k++)
                if(k) f[i][j]=min(f[i][j],f[j][k]+s[i]-s[j+1]+abs(a[k]-a[j+1]));
                else f[i][j]=min(f[i][j],f[j][k]+s[i]-s[j+1]);
    }
    int ans = 0x3f3f3f3f;
    for(i=1;i<=n;i++) ans=min(ans,f[n][i]);
    printf("%d\n",ans);
}

要避免这种情况其实很简单，方程不需要改，只需要更改一下求解的顺序即可。首先观察一下上述的公式，

由于在求f[i][j]时，i,j可以看做是已知数，因此，可以把s[i][j]从min()中提出来，变成

没错，提出来之后，min()内的部分只和j,k有关，与i无关。因此，在计算任意的f[x][j]时，min()部分的值实际上是完全相同的，这部分只需要j确定，就能在o(n)的时间内算出来，而算出来之后，计算所有的f[x][j]，都只需要o(1)的时间。
调整后的代码为：

void dp()
{
    int i,j,k;
    memset(f,0x3f,sizeof(f));
    mem(s);
    f[0][0]=0;
    for(i=2;i<=n;i++) s[i]=s[i-1]+abs(a[i]-a[i-1]);
    for(i=1;i<=n;i++) f[i][0]=s[i];
    for(j=1;j<n;j++)//f[i][j] =s[i]-s[j+1]+ G;
    {
        int G = 0x3f3f3f3f;
        for(k=0;k<j;k++)
            if(k) G=min(G,f[j][k]+abs(a[k]-a[j+1]));
            else G=min(G,f[j][k]);
        for(i=j+1;i<=n;i++)
            f[i][j]=min(f[i][j],s[i]-s[j+1]+G);
    }
    int ans = 0x3f3f3f3f;
    for(i=1;i<=n;i++) ans=min(ans,f[n][i]);
    printf("%d\n",ans);
}