动态规划

第一步：确定状态（确定dp数组及含义）

数值型dp[i][j]：表示从数组下表i到下表j之间数字的最大值。

第二步：转移方程

在确定递推公式时，就要分析如下两种情况获得dp[i][j]的值。
第一种是dp[i][k]+dp[k+1][j]两者相加的结果其中k取值范围为[i,j);
第二种是dp[i][k]*dp[k+1][j]两者相乘的结果.
那么递归公式如下:  

    dp[i][j] = max(dp[i][j],max(dp[i][k]+dp[k+1][j], dp[i][k]*dp[k+1][j]));

第三步：初始条件和边界情况

dp[i][i]代表的是数组中下表为i的数值；
所以初始化dp[i][i] = ret[i];

for(int i = 0; i < len; ++i)
        dp[i][i] = ret[i];

第四步：确定遍历顺序

for(int i = 0; i < len; ++i)
    {
        for(int j = i; j < len; ++j)
        {
            for(int k = i; k < j; ++k)
               ......
        }
    }

C++程序

#include <iostream>
#include <vector>
using namespace std;

int getMaxValue(vector<int>ret, int len){
    if(len <= 0 )
        return 0;
    vector<vector<int>>dp(len,vector<int>(len,0));
    for(int i = 0; i < len; ++i)
        dp[i][i] = ret[i];
    for(int i = 0; i < len; ++i)
    {
        for(int j = i; j < len; ++j)
        {
            for(int k = i; k < j; ++k)
                dp[i][j] = max(dp[i][j],max(dp[i][k]+dp[k+1][j], dp[i][k]*dp[k+1][j]));
        }
    }
    return dp[0][len-1];
}
int main(){
    int num1, num2, num3;
    while(cin>>num1>>num2>>num3)
    {
        int maxValue = 0;
        vector<int>ret{num1,num2,num3};
        maxValue = getMaxValue(ret,ret.size());
        cout<<maxValue<<endl;   
    }
    return 0;
}