1170能量项链(dp动态规划）

解题思路:
看到最大值，就想到最优解，想到最优解就想到动态规划。将大问题分成一个个小问题来看。先求两个球能得到的能量，再求三个球时，四个球时，

第一步，要得到两个球的能量，我们就需要三个数，这是第一层循环。

第二步 要得到从不同球开始的两个球的能量，我们就要改变  头球的位置，这是第二层循环，

第三步，我们要计算出两个球之间的能量，当两个球的时候好办，可是如果是3个球的时候，你可能就有点不理解了，

这时你得到了4个数，要求这时的最优解，为什么是dp[tou][k]+dp[k][rear] + arr[tou] * arr[k] * arr[rear]，

这里它就是从tou的位置到rear-1的位置 (也就是k的值）去遍历抵达到rear时的最优值，然后又要看从tou到k 的最优值，从k 到 rear 的最优值，最后还要加上没有算进去的能量值。

由于我不会画图工具，所以这解释起来有亿点点抽象。

所以dp就像一个巨大的套娃。太难了！

注意事项:

参考代码:

#include<iostream>

using namespace std;

int arr[210];

int dp[210][210];

int main()

{

int n;

cin >> n;

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

{

cin >> arr[i];

arr[i + n] = arr[i];

}

for (int len = 3; len <= n + 1; len++)

{

for (int tou = 1; tou + len - 1 <= 2 * n; tou++)

{

int rear = len + tou - 1;

for (int k = tou + 1; k < rear; k++)

dp[tou][rear] = max(dp[tou][rear], dp[tou][k]+dp[k][rear] + arr[tou] * arr[k] * arr[rear]);

}

}

int MAX = 0;

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

{

MAX = max(MAX, dp[i][i+n]);

}

cout << MAX << endl;

return 0;

}