标签搜索

目 录CONTENT

文章目录

美团--合并金币.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 1,680 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

美团--合并金币

@[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;
}
0

评论区