时间和空间复杂度皆为O(mn)。
下面再分析一个具体的编程问题，使用动态规划算法，但是和上面的DP又有一些区别。
合唱团问题 问题定义有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述
输出一行表示最大的乘积。
问题分析此题的第一个关键点是“要求相邻两个学生的位置编号的差不超过 d”，如果按照传统的DP思路，定义opt(i,k)表示在前i个学生中选取k个学生的最大乘积，建立递推关系:
则无法实现“相邻两个学生的位置编号的差不超过 d”的要求。因此，需要定义一个辅助量，来包含对当前学生的定位信息。
定义f(i,k)表示在前i个学生中选取k个学生，且第i个学生必选时，所选学生的能力值乘积，这样就包含对当前学生的定位信息，f的递推关系可以表示为
其中，j是一个比i小的值，最大为i-1，i、j之差不超过D，f(j,k-1)表示在前j个学生中，选择k-1个学生，且第j个学生必选。f(i,k)选择了第i个学生，f(j,k-1)选择了第j个学生，i、j之差不超过D，这样就可以满足题目要求了。
辅助量f(i,k)并不是我们最终要得到的结果，最终结果opt(i,k)表示在前i个学生中选取k个学生的最大乘积，因此，可以得到opt(i,k)和f(i,k)的关系为：
该问题的第二个关键点是学生的能力值在-50到+50之间，每次选择的学生的能力值有正有负，所以需要两个f记录最大和最小值，定义fmax和fmin，在每次迭代f的过程中：
当k=K，i=N时，最终所求的:$$opt(N,K)=max_i(f(i,K)),K<=i<=N$$
边界条件k=1时，f(i,k=1)=v(i)
代码实现 /********************************************************************* * * Ran Chen <wychencr@163.com> * * Dynamic programming algorithm * *********************************************************************/ #include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; int main() { int N, D, K; // 总共N个学生 vector <int> value; while (cin >> N) { for (int i = 0; i < N; ++i) { int v; cin >> v; value.push_back(v); } break; } cin >> K; // 选择K个学生 cin >> D; // 相邻被选择学生的序号差值 // fmax/fmin[i, k]表示在选择第i个数的情况下的最大/小乘积 vector <vector <long long>> fmax(N+1, vector <long long> (K+1)); vector <vector <long long>> fmin(N+1, vector <long long> (K+1)); // 边界条件k=1 for (int i = 1; i <= N; ++i) { fmax[i][1] = value[i - 1]; fmin[i][1] = value[i - 1]; } // 自底向上dp, k>=1 for (int k = 2; k <= K; ++k) { // i >= k for (int i = k; i <= N; ++i) { // 0 <= j <= i-1 && i - j <= D && j >= k-1 long long *max_j = new long long; *max_j = LLONG_MIN; long long *min_j = new long long; *min_j = LLONG_MAX; // f(i, k) = max_j {f(j, k-1) * value(i)} int j = max(i - D, max(k - 1, 1)); for ( ; j <= i - 1; ++j) { *max_j = max(*max_j, max(fmax[j][k - 1] * value[i - 1], fmin[j][k - 1] * value[i - 1])); *min_j = min(*min_j, min(fmax[j][k - 1] * value[i - 1], fmin[j][k - 1] * value[i - 1])); } fmax[i][k] = *max_j; fmin[i][k] = *min_j; delete max_j; delete min_j; } } // opt(N, K) = max_i {f(i, K)}, K <= i <= N long long *temp = new long long; *temp = fmax[K][K]; for (int i = K+1; i <= N; ++i) { *temp = max(*temp, fmax[i][K]); } cout << *temp; delete temp; system("pause"); return 0; }