合唱

典型的序列型DP，思路可以参考高赞回答@buaaqlyj或者@夭寿啦要没Offer啦
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n; cin >> n;
    int *data = new int[n];
    cin >> data[0];
    int *DP = new int[n*n];
    int sum = 0;
    for (int i = 1; i < n; i++) {
        cin >> data[i];
        DP[i*n + i - 1] = sum;
        sum += abs(data[i] - data[i - 1]);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i - 1; j++) {
            DP[i*n + j] = DP[(i - 1)*n + j] + abs(data[i] - data[i - 1]);
        }
        for (int k = 0; k < i - 1; k++) {
            DP[i*n + i - 1] = min(DP[i*n + i - 1], DP[(i - 1)*n + k] + abs(data[i] - data[k]));
        }
    }
    int result = DP[(n - 1)*n];
    for (int i = 1; i < n - 1; i++) {
        result = min(result, DP[(n - 1)*n + i]);
    }
    cout << result;
    delete[] DP;
    return 0;
}

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int v[2010],n,dp[2010][2010];
int d(int,int);
int main() {
    scanf("%d",&n);
    v[0]=-1;
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",d(0,0));
}
int d(int i,int j){
    int k=max(i,j)+1;
    if(k==n+1) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    dp[i][j]=999999999;
    dp[i][j]=min(dp[i][j],d(k,j)+(i?abs(v[k]-v[i]):0));
    dp[i][j]=min(dp[i][j],d(i,k)+(j?abs(v[k]-v[j]):0));
    return dp[i][j];
}//记忆搜索 dp[i][j]表示 小Q和牛博士上一个音调分别为v[i]和v[j]

var len = Number(readline())
var list = readline().split(' ').map(x=>Number(x))
if(len<3){
    print(0)
}else{
    var dp = new Array(len).fill(1).map(_=>[0])
    var sum = new Array(len).fill(0)  //考虑前面i-1种音调由一个人唱时
    for(let i=2;i<len;i++){
        sum[i] = sum[i-1]+Math.abs(list[i-1]-list[i-2])
        dp[i][i-1] = sum[i]
        for(let j=0;j<i-1;j++){
            dp[i][j]=dp[i-1][j]+Math.abs(list[i]-list[i-1])
            dp[i][i-1] = Math.min(dp[i][i-1],dp[i-1][j] + Math.abs(list[i]-list[j]))
        }
    }
    print(Math.min(...dp[len-1]))
}

js版本，思路参考 buaaqlyj 的回答

令dp[i][j]表示某一个人最近唱的音为第i个，另一个人最近唱的是第j个时最小的难度

则实现如下规律即可

当j=i-1时：
考虑前面i-1种音调由一个人唱时 
dp[i][j]_1 = sum{list[i]-list[i-1]},i∈[1,len-2] (第一个 到 倒数第二个音调之间的差值总和)
考虑前面i-1种音调由两个人唱时
dp[i][j]_2 = min{ dp[k][j] + |list[i]-list[k]| } 
           = min{ dp[i-1][k] + |list[i]-list[k]| },k∈[0,i-2]
dp[i][j] = min{dp[i][j]_1,dp[i][j]_2}

当j≠i-1时：
dp[i][j] = dp[i-1][j] + |list[i]-list[i-1]|

最后求出min{dp[i][k]},k∈[0,i-1]

	// 参考了上面各位大神的思路，得出递推公式：



	// dp[i][i-1] = min(dp[i-1][k] + abs(v[i] - v[k])),(0<=k<j)



	// dp[i][j] = dp[i-1][j] + abs(v[i] - v[i-1]), (i-1>j)



	// 有边界条件，dp[1][0]=0;



	// dp[1][0]=>dp[1...n-1][0]



	// dp[1][0],dp[2][0]=>dp[2][1]=>dp[2...n-1][1] 



	// ......



	// dp[1...n-2][0...n-2]=>dp[n-1][n-2]



	// 类推，可以得到所有[i,j]的值，找出dp[n-1][]中最小值即可。



	#include<stdio.h>



	#include<stdlib.h>



	#define MaxN 2000



	int n;



	int v[MaxN]={0};



	int dq[MaxN][MaxN]={0};



	void work(){



	    dq[1][0] = 0;



	    for (int j=0; j<n-1; j++) {



	        for (int i=j+2; i<n; i++) {



	            dq[i][j] = dq[i-1][j]+abs(v[i]-v[i-1]);



	        }



	        if (j+2<n) {



	            dq[j+2][j+1]=dq[j+1][0]+abs(v[1]-v[0]);



	            for (int k=0; k<j+1; k++) {



	                int tmp=dq[j+1][k]+abs(v[j+2]-v[k]);



	                dq[j+2][j+1]= dq[j+2][j+1]<=tmp ? dq[j+2][j+1] : tmp;



	            }



	        }



	    }



	    int result=dq[n-1][0];



	    for (int i=1; i<n-1; i++) {



	        result = result<=dq[n-1][i] ? result : dq[n-1][i];



	    }



	    printf("%d",result);



	}



	int main(){



	    scanf("%d",&n);



	    for(int i=0;i<n;i++){



	        scanf("%d",&v[i]);



	    }



	    work();



	}

一点点思考的过程，感觉有点乱，记录下来

第一个维度是当前一个人唱第i个位置的音符，第二个维度不好找。第二个维度如果也是音符的话，那么就必须有先后关系。第二个维度是另一个人之前唱到的音符，c[i][j]是此时最小难度和。

c[i][j]可能由哪些状态转移过来呢？
例如某人唱到了第6个音符，另一个人最后一次唱到了第3个音符，此时如果当前的总的难度是最小的，那么有以下结论：
第6个音符、第5、第4个音符都是第一个人唱的。因为第二个人才唱到了第三个音符，他不可能去唱后面的音符。
所以c[6][3] = c[5][3] + 56难度差。
但是c[4][3]是怎么转移来的呢？如果此时第一个人唱到了第4个音符，另一个人唱到了第3个音符，这说明第一个人唱第4个音符中断了第二个人唱的音符。由于不知道上一次第一个人是从哪里跳到第4个音符的，所以我们分别假设是从可能的所有音符跳过来的，如果是从第二个音符跳过来的，那么就是c[3][2]+ 34差。如果是从第一个音符跳过来的，那么就是c[3][1]+14差。如果是从没有跳过来的，那么就是c[3][0]+04差。由于第一个人唱的时候，第二个人上一次唱的总是比第一个人唱的要小，所以我们不需要考虑j>=i的时候。

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <array>

using namespace std;

vector<int> nums;
array<array<int, 2100>, 2100> dp;

// 计算两个音符之间的难度。注意第一个音符的下标在输入数据里面是0，有个差1的关系。如果起始音符是0，说明第一次唱，不增加难度 */
int diffcult(int s, int e)
{
    if(s == 0) return 0;
    // printf("diffcult %d %d to %d %d is %d \n", s,nums[s-1], e,nums[e-1], abs(nums[e-1] - nums[s-1]));
    return abs(nums[e-1] - nums[s-1]);
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }

    ///* 从0开始向后考虑，直到考虑完所有音符，第一个人最差的情况是没有唱，此时j也没有唱，直接continue了 */
    for (int i = 0; i <= n; i++)
    {
        ///* 这里也是从0开始考虑，因为第一个人最差一个都不唱，就是处于0 */
        for (int j = 0; j <= n; j++)
        {
            ///* 不考虑后面的情况。当然也可以直接写到上面的范围限制里面 */
            if (j >= i)
                continue;
            ///* 如果是一般情况下，比如第一个人在唱6音符时，第二个人在唱3音符，显然是从dp[5][3]转移来的 */
            if (j + 1 < i)
            {
                dp[i][j] = dp[i - 1][j] + diffcult(i - 1, i);
            }
            ///* 否则，如果第二个人刚唱完就被第一个人抢唱了，那么第一个人唱的音符就可能是前面跳过来的 */
            if (j + 1 == i)
            {
                ///* k表示i是从第几个跳过来的 */
                int min_cost = -1;
                for (int k = 0; k < j; k++)
                {
                    int cost = dp[j][k] + diffcult(k, j + 1);
                    ///* 只用记录最小跳唱难度 */
                    if(min_cost == -1 || min_cost > cost){
                        min_cost = cost;
                    }
                }
                if(min_cost == -1) min_cost = 0;
                dp[i][j] = min_cost;
            }
            // 调试代码，打开可以看推导过程
            // for(int a=0;a<=n;a++){
            //     for(int b=0;b<=n;b++){
            //         if(a==i && b == j){
            //             printf("\t【%d】", dp[a][b]);
            //         }
            //         else printf("\t%d", dp[a][b]);
            //     }
            //     // printf("\n");
            // }
            // printf("\n");
        }
    }
    int min_cost = -1;
    for(int j=0;j<n;j++){
        if(min_cost == -1 || min_cost > dp[n][j]){
            min_cost = dp[n][j];
        }
    }
    printf("%d", min_cost);
}

动态规划题

1. dp[i][j]（永远有i > j）表示某一个人最近唱的音为第i个，另一个人最近唱的是第j个时最小的难度
2. 由于只由一个人唱完肯定不是最优解。因此先在一个for循环内确定以下两种情况的初值
   dp[i][0]：第二个人唱第一个音，第一个人唱后面所有音
   dp[i][i-1]：第一个人唱最近的一个音，第二个人唱前面所有音

3. dp[i][j]转移方程
   每当交换唱歌次序，两人最近一次唱的音符一定是相邻的，所以底下分相邻和不相邻讨论：
   (1). 当j == i - 1，即交换唱歌次序，dp[i][i-1]时，表明第一个人上一个音可能在第k个音（0 <= k < i-1）,由唱了最近的第i个，第二个人仍然留在第i-1个音。
   dp[i][i-1] = 对所有k求min(dp[i-1][k] + abs(arr[i] - arr[k]) ) 其中（0 <= k < i-1）
   (2). 当j < i - 1，即不交换唱歌次序时，只可能由唱到i-1音符的人续唱
   dp[i][j] = dp[i-1][j] + abs(arr[i] - arr[i-1])

4. 最后求出所有dp[len-1][]里的最小值即为全局最优解

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int len = in.nextInt();
            int[] arr = new int[len];
            for (int i = 0; i < len; ++i) {
                arr[i] = in.nextInt();
            }
            if (len < 3) {
                System.out.println("0");
            } else {
                int[][] dp = new int[len][len];
                int[] acc = new int[len];
                dp[0][0] = 0 - Math.abs(arr[1] - arr[0]);
                for (int i = 1; i < len; ++i) {
                    acc[i] = acc[i - 1] + Math.abs(arr[i] - arr[i - 1]);
                    dp[i][i - 1] = acc[i - 1];
                    for (int j = 0; j < i - 1; ++j) {
                        dp[i][j] = dp[i - 1][j] + acc[i] - acc[i - 1];
                        dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + Math.abs(arr[i] - arr[j]));
                    }
                }
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < len - 1; ++j) {
                    min = Math.min(min, dp[len - 1][j]);
                }
                System.out.println(min);
            }
        }
    }
}

• 可先设 dp[i][j] 表示当前小Q唱到第 i 个音调，牛博士唱到第 j 个音调的难度和；
• 不妨设当前 i > j ：
  • 若 i - 1 == j 则发生换人，由于不知道上一次 i 唱到哪里，状态由 min{ dp[k][j] + abs(v[i] - v[k]) }, k < j 转移来；
  • 若 i - 1 > j 则表示当前是从 i - 1 唱到 i 的，没有换人，状态由 dp[i-1][j] + abs(v[i] - v[i-1]) 累加；
• 不妨设 dp[i][j] 表示当前演唱到第 i 个，上一个人演唱到第 j 个，则状态转移方程为
  dp[i][j] = dp[i-1][j] + abs(v[i] - v[i-1]), j < i - 1
  dp[i][i -1] = min{ dp[i-1][k] + abs(v[i] - v[k]) }, k < i - 1
• 初始情况是若当前有 i 个音调，可以让一个人只唱第一个或最后一个音调，剩下的音调都由另一个人唱：
  dp[i][0] = dp[i-1][0] + abs(v[i] - v[i-1]), i ≥ 2
  dp[i][i-1] = dp[i-1][i-2] + abs(v[i-1] - v[i-2]), i ≥ 2

• 设 dp[i][j] 表示从当前小Q唱到第 i + 1 个音调，牛博士唱到第 j + 1 个音调开始，直到所有音调演唱完的难度和；边界情况 i = 0 或 j = 0 表示一个人还没开始唱；
• 容易知道下一个音调 next = max{ i, j } ，若让小Q唱下一个音调，会得到 abs(v[next] - v[i]) 的贡献；若让牛博士唱会得到 abs(v[next] - v[j]) 的贡献；
• 状态转移方程
  dp[i][j] = min{ dp[next][j] + abs(v[next] - v[i]), dp[i][next] + abs(v[next] - v[j]) }, i ≠ j < n

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

typedef long long llong;

inline void getMin(llong& n, llong x) {
    n > x && (n = x);
}

#define MAXN 2020

int n;
int v[MAXN], cost[MAXN];

void read() {
    scanf("%d%d", &n, v);
    for (int i = 1; i < n; ++i) {
        scanf("%d", v + i);
        cost[i] = abs(v[i] - v[i - 1]);
    }
}

llong dp[MAXN][MAXN];

void work() {
    llong res = (1ll << 63) - 1;
    for (int i = 2; i < n; ++i) {
    //    dp[i][0] = dp[i - 1][0] + cost[i];
        dp[i][i - 1] = dp[i - 1][i - 2] + cost[i - 1];
    }
    for (int i = 2; i < n; ++i) {
        for (int j = 0; j < i - 1; ++j) {
            dp[i][j] = dp[i - 1][j] + cost[i];
            getMin(dp[i][i - 1], dp[i - 1][j] + abs(v[i] - v[j]));
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        getMin(res, dp[n - 1][i]);
    }
    printf("%lld\n", res);
}

int main() {
    read();
    work();
    return 0;
}

using std::max;
using std::min;

int n, v[MAXN];

void read() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", v + i);
    }
}

int cost(int a, int b) {
    return a && b ? abs(v[a] - v[b]) : 0;
}

llong solve(int i, int j) {
    int next = max(i, j) + 1;
    if (next == n + 1) {
        return 0;
    }
    if (!~dp[i][j]) {
        dp[i][j] = min(solve(next, j) + cost(next, i), solve(i, next) + cost(next, j));
    }
    return dp[i][j];
}

void work() {
    memset(dp, 0xff, sizeof(dp));
    llong res = solve(0, 0);
    printf("%lld\n", res);
}

void work() {
    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int next = max(i, j) + 1;
            dp[i][j] = min(dp[next][j] + cost(next, i), dp[i][next] + cost(next, j));
        }
    }
    printf("%lld\n", dp[0][0]);
}

给像我这样的菜鸟,做一个动态规划的傻瓜式讲解.用的还是上面大佬们的思想

假设有n个数字,从1开始每次加一个,去掉绝对最差的.

比如 (3,4):5 (4,3):7 (3,4):8 仅保留(3,4):5

设置 m[i=5][j=5] 代表在放入第i个数时,一人最后一唱为i,另一人为j (j<i)

思想: 一生二,二生四(去除相同,取最小),三生六.....

举例

输入:

5

1 5 6 1 2

1. (1,0):0

2. (2,0):|1-5|=4 (2,1):0

----2的俩项由1生成

1. (3:0):5 (3:2):4 (3,1):1 (3,2):5

----3的四项由2的俩项生成,其中重复的(2,3)取最小

......直到去取完

可以发现,比如

                   (4,0)生成(5,0) (5,4)
                   (4,1)生成(5,1) (5,4)
                   (4,2)生成(5,2) (5,4)
                   (4,3)生成(5,3) (5,4)

即可以直接在m[i+1]中直接加入m[i]中的生成的前 i 项,最后一位为相同项的最小值.

```
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n,tmp; cin >> n;
    vector<int> x(n);
    vector<vector<int>> m(n);
    vector<int> arr;
    m[0].push_back(0);
    cin >> x[0];
    for (int i = 1; i < n ; i++)
    {
        cin >> x[i];
        m[i].push_back(m[i - 1][0] + abs(x[i] - x[i - 1]));
        arr.push_back(m[i - 1][0]);
        for (int j = 1; j < i; j++)
        {
            m[i].push_back(m[i-1][j] + abs(x[i-1] - x[i]));
            arr.push_back(m[i-1][j] + abs(x[j-1] - x[i]));
        }
        tmp = *min_element(arr.begin(), arr.end());
        m[i].push_back(tmp);
        arr.clear();
    }
    /*查看m表
    for (auto p : m)
    {
        for (auto k : p)
            cout << k << " ";
        cout << endl;
    }
    */
    int ans = *min_element(m[n - 1].begin(), m[n - 1].end());
    cout << ans;
    system("pause");
}

py3版本：
n=int(input())
ns=[int(i) for i in input().split(' ')]
dp=[[0]*n  for i in range(n)]
#特殊位置初始化
for i in range(2,n):
    dp[i][0]=dp[i-1][0]+abs(ns[i]-ns[i-1])
    dp[i][i-1]=dp[i-1][i-2]+abs(ns[i-1]-ns[i-2])
#逐步动态规划
for i in range(2,n):
    for j in range(i-1):
        dp[i][j]=dp[i-1][j]+abs(ns[i]-ns[i-1])
        dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+abs(ns[i]-ns[j]))
print(min(dp[-1][:n-1]))

#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <vector>
#include "algorithm"
#include <set>
#include <stdlib.h>
using std::cin;
using std::cout;
using  std::endl;
using  std::string;
using  std::pair;
using std::vector;

/*
 * ddepth[i][j]=depth[j][i] 所以这个矩阵是对称矩阵 所以我们在处理的时候只需要处理下班部分就行了 所以可以提出简化条件 j<i
 * -------> depth[i][j]=min ( depth[x][j] + abs(value_i-x) )
 */

int min(int &a,int &b)
{
    return  a<b?a:b;
}

int ab(int a)
{
    return a>0?a:-a;
}

int main()
{
    int n=0;
    cin>>n;
    vector<int> list(n+1,0);  //不要list第一个数
    vector<vector<int>> depth(n+1,vector<int>(n+1,0));
    for (int i = 1; i <=n; ++i)
    {
        cin>>list[i];
    }
    depth[1][0]=depth[0][1]=list[0];

    //正式进入dp递归的算法
    for(int i=2;i<n+1;i++)   //最外层的循环每一层都是一个边界
    {
        for (int j = 0; j <i ; ++j)
        {
            int sum=-1;
            // 上一步是交给了B
            if(j==i-1)
            {

                for (int k = 0; k < j; ++k)
                {
                    int result=0;

                    if(k!=0)
                        result=depth[k][j]+ab(list[i]-list[k]);
                    else
                        result=depth[k][j];  //k=0 A增加点 不增加难度

                    if(sum==-1) sum=result;
                    else sum=min(sum,result);
                }
            } else{
                //上一步还是自己走的
                sum=depth[i-1][j]+ab(list[i]-list[i-1]);
            }
            depth[i][j]=sum;
            depth[j][i]=sum;
        }
    }
    int final=depth[n][0];
    for (int l = 1; l <n ; ++l)
    {
        final=min(depth[n][l],final);
    }
    cout<<final<<endl;

}

	

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];//保存音调
        int[] cost = new int[n];//保存音调差的总和，cost[1] = Math.abs(arr[1] - arr[0]) + cost[0]
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if(i >= 1)cost[i] = Math.abs(arr[i] - arr[i-1]) + cost[i-1];
        }
        if(n < 3)System.out.println(0);
        else {
            //定义二维数组dp[n][n],其中dp[i][j]表示其中一个人最后唱第i个，另一个人最后唱第j个的时候的最小代价。(i>j)
            int[][] dp = new int[n][n];
            dp[1][0] = 0;//一个人最后唱的是第1个，一个人最后唱的是第0个
            for(int i = 2; i < n; i++) {
                dp[i][i-1] = cost[i-1];//一个人唱第i个，前面0到i-1让另一个人唱,没有交叉的情况，不能保证代价最小。
                //下面的循环为了求出dp[i][0]....dp[i][i-1],有交叉的情况。
                for(int k = 0; k < i-1; k++) {
                    //假设第一种情况：A要唱第i个，B最后唱的在第k个，k从0到i-2,说明第i-1个肯定也是A唱的
                    dp[i][k] = dp[i-1][k] + cost[i] - cost[i-1];
                    //假设第二种情况：A要唱第i个，B最后唱的是第i-1个，那么A上一次唱的肯定是在第0到i-2个之间
                    dp[i][i-1] = Math.min(dp[i][i-1], dp[i-1][k] + Math.abs(arr[i] - arr[k]));
                }
            }
            int min = Integer.MAX_VALUE;
            //因为dp[i][j]中i>j,所以循环到n-2就停止，要不然最小值输出为0
            for(int i = 0; i < n - 1; i++) {
                min = Math.min(dp[n-1][i], min);
            }
            System.out.println(min);
        }
    }
}

/*
 * 参考大神的解题思路：https://www.nowcoder.com/questionTerminal/fddf64d5757e41ec93f3ef0c0a10b891
 * 使用动态规划，dp[i][j]表示最近一次第一个人唱的是i，第二个人唱的是j
 * 不妨设置i>j:
 * 当j = i-1，说明发生了交换的情况，dp[i][j] = dp[i-1][k]+min(abs(nums[i]-nums[k])), 0<=k<i-1;
 * 当j<i-1，说明唱i字符的时候没有发生交换的情况,dp[i][j] = dp[i-1][j]+abs(nums[i]-nums[i-1])
 * */
public class Chorus {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
            }
            int[] acc = new int[n];
            int[][] dp = new int[n][n];
            for (int i = 1; i < n; i++) {
                acc[i] = acc[i - 1] + Math.abs(nums[i] - nums[i - 1]);
//                初始化dp[i][i-1]
                dp[i][i - 1] = acc[i - 1];
                for (int j = 0; j < i - 1; j++) {
//                    第一种情况
                    dp[i][j] = dp[i - 1][j] + acc[i] - acc[i - 1];
//                    第二种情况
                    dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + Math.abs(nums[i] - nums[j]));
                }
            }
//            统计最小值
            int min = dp[n - 1][0];
            for (int i = 1; i < n - 1; i++) {
                min = Math.min(min, dp[n - 1][i]);
            }
            System.out.println(min);
        }
    }
}