算法分析 | 动态规划 | 石子合并问题

一.问题描述

在一条直线上有n堆石子, 要求每次将相邻的两堆石子合成一堆,花费=两堆石子的总数

求最省总花费.

因为存在相邻的限制条件,不能使用贪心算法将每次最小的2堆合起来.遂使用动态规划

 

二.代码实现

1.StoneMerge.h

#pragma once
#include"allh.h"
//石子合并问题(直线型)  一条直线上只有相邻的石子堆可以合并.合并i堆和j堆的花费w=i+j

vector<int> stone = { 5,8,6,9,2,3 };//记录每个石子堆的数量
int SN = stone.size();
vector<int>tempSto(SN,0);
//记录最优解
vector<vector<int>>bestSto(SN, tempSto);
//记录最优策略
vector<int>tempP(SN, -1);
vector<vector<int>>bestP(SN, tempP);
vector<int> sum(SN+1);



//石子合并执行函数
int MergeStone()
{
	//sum[i]表示前i堆的合并花费,要有sum[0]来应对 i=1时"sum[j]-sum[i-1]"
	sum[0] = 0;		
	for (int i = 1; i <= SN; i++)		//记录sum[1]~sum[6]
	{
		sum[i] = sum[i - 1] + stone[i - 1];
		cout << i <<"	"<< sum[i]<<endl;
	}
	//一堆石子不能合并,bestSto[i][i]=0
	for (int i = 0; i < SN; i++)  //记录bestSto[0][0]~[6][6]
		bestSto[i][i] = 0;

	//开始记录
	for (int scale = 2; scale <= SN; scale++)  //合并2堆石子的最优解->合并SN堆石子的最优解
	{
		for (int i = 0; i <= SN - scale; i++)		//例如规模==2,堆数==6 则  0≦i≦4
		{
			int j = i + scale - 1;  //scale个石子堆的最后一个

			int k = i;
			bestSto[i][j] = bestSto[i][k] + bestSto[k + 1][j] + sum[j+1]-sum[i];
			bestP[i][j] = k;

			for ( k = i+1; k < j; k++)
			{
				int t = bestSto[i][k] + bestSto[k+1][j] + sum[j+1] - sum[i];
				if (t < bestSto[i][j])
				{
					bestSto[i][j] = t;
					bestP[i][j] = k;
				}
			}
		}
	}

	for (int i = 0; i < SN; i++)
	{
		for (int j = 0; j < SN; j++)
		{
			cout << bestP[i][j]<<"\t";
		}
		cout << endl;
	}
	return bestSto[0][SN - 1];
}

void StoPrint(int i, int j)
{
	if (i == j)
	{
		cout << i;
		return;
	}
	else
	{
		cout << "(";
		StoPrint(i, bestP[i][j]);
		StoPrint(bestP[i][j] + 1, j);
		cout << ")";
	}
}

2.main()

	cout << endl << "最小石子合并花费为：" << MergeStone() << endl << endl;
			cout << "合并次序为：" << endl;
			StoPrint(0, SN-1);

 结果为:

三.Bug分析

1.打印函数StoPrint(int i,int j)

bestP[ i ] [ j ] = k 表示子问题 { i 堆合并到 j 堆}的最小花费策略是( i ~ k ) ( k+1 ~ j )

Q:StoPrint()什么时候return呢?

A:当递归到只剩下单个元素时,即i==j

先写中断条件:

if (i == j)
	{
		cout << i;
		return;
	}

再写递归状态:

希望按照(子问题1)(子问题2)的方式打印

else
	{
		cout << "(";
		StoPrint(i, bestP[i][j]);
		StoPrint(bestP[i][j] + 1, j);
		cout << ")";
	}

2.边界问题:

善用断点功能.

先定位哪一行出了问题->①确定是数组的最后一个溢出

                                       ②数组最后一个未遍历

 

---

UPDATE:圆形石子合并问题,实际上转换成2N-1的直线型问题

此时,不光要求堆( 1 ~ N )的最优解,还要求( 2 ~ N+1 ) 、(3 ~ N+2 )... ... ( N ~ 2N-1)的最优解,并找出最小值

只需在直线型的代码中将N->2N-1即可

不过只能得到最优解 , Print()函数怎么写还是个问题.