美团--合并金币

@[toc]

一、题目描述

同样还是两道一样的题！！！

二、分析

•  拿到题目，看到相邻两字，就考虑动态规划问题。
•  这里第一步确定dp[i][j]是什么意思，我这里规定dp[i][j]就是从第i个位置开始到第j个位置结束，这一堆合并金币所需的最小成本。
•  第二步 确定状态转移方程

打个比方说如果输入4个数 2 3 6 1（为了方便理解，我把下标定为从1开始 到4结束）
那我们就先比方说dp[1,3]也就是从第一个位置到第三个位置结束，那也就是2 3 6的最小成本数，我们有两种情况：
从2到3 是一堆，然后6是一堆；
2是一堆，3 到6是一堆。
那么我们这个dp[1][3]的公式就是dp[1][2]+dp[3][3]+2+3+6或dp[1,1]+dp[2][3]+2+3+6；
后面的2+3+6的意思是最后一次的成本数，也就是不管你是从哪个开始到哪个结束，最后一次的成本永远是从开始到结束的总和。

比如说如果是从2 3为一堆先开始，那就是2 3 6=>5 6(5)=>11(5+11) 括号里是成本数。

•  那我们现在可以确定dp[i][j]的公式就是设置一个变量k；i<=k<j，dp[i][j]=dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + lastMoney); 这个k是放在循环里的。
•  接下来就是具体怎么放到代码当中了
•  既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。
•  所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。
•  然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

//枚举长度
for(int len = 1;len <= n;len++)
{
		//枚举起点，ends<=n
        for(int j = 1;j + len <= n + 1;j++)
        {
            int ends = j + len - 1;
            //枚举分割点，更新小区间最优解
            for(int i = j;i < ends;i++)
            {
                dp[j][ends] = min(dp[j][ends],dp[j][i] + dp[i + 1][ends] + something);
            }
        }
    }

•  第三部 给出base case

for(int i = 1; i <= n ;i++)    
    	dp[i][i] = 0;

•  因为还没合并，花费当然为0喽

三、代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 105;
int n;
int num[maxn]={0};
int dp[maxn][maxn]={0};
int cost[maxn][maxn]={0};

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)   
    	cin>>num[i];

    memset(dp,0x3f,sizeof(dp));

    //花费初始化
    for(int i = 1; i <= n;i++)
    {
        for(int j = i; j <= n ;j++)
        {
            for(int k = i; k <= j; k++)
            {
                cost[i][j] += num[k];
            }
        }
    }

	//base case
    for(int i = 1; i <= n ;i++)    
    	dp[i][i] = 0;

    //枚举每个小区间，小区间的长度为len
    for(int len = 2; len <= n;len++)
    {
    	//小区间的起始位置
        for(int l = 1; l <= n - len + 1 ;l++)
        {
        	//小区间的结束位置
            int r = l + len - 1;

			//枚举该区间内的最优解
            for(int k = l ; k < r; k++)
            {
                dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r] + cost[l][r]);
            }
        }
    }

    cout<<dp[1][n]<<endl;
    return 0;
}