（实用）马里奥最新游戏规则：输出最好的单词

首先，他从书中随机挑选了一个单词。 然后他将其拆分在任意两个位置，从而形成三个单独的单词。

随后，他颠倒了这三个单词中每个字母的顺序（交换第一个和最后一个字母，第二个和倒数第二个字母，等等）。

最后，他将这三个词按照分开前的顺序重新拼凑在一起。 游戏的目标是获得尽可能小的单词。 也就是说，在上述过程能够得到的所有单词中，找到字典中最早的单词。

编写一个可以完美玩马里奥游戏的程序。

输入格式：

输入的第一行也是唯一一行包含单词 Mario ，它是英文字母表中的一串小写字母，不带空格。

输入单词的长度在 3 到 50 个字符之间（含）。

输出格式：

输出最好的单词。

输入示例1：

dcbagfekjih

输出样本1：

abcdefghijk

输入示例2：

mobitel

输出样本2：

bometil

输入示例3：

anaconda

输出样本3：

aanadnoc

解决问题的思路：

用循环的方法将每次打乱的单词在不同的地方进行切割。 每次剪切后都会得到三个单词，然后根据题中的提示再次拼接，最后得到一个新单词。 采用动态规划的方式，将每个新循环得到的结果与上一个循环得到的结果进行比较，选择最小的单词，继续迭代，直到得到最小的单词。

显示dp表：

这道题的思路和矩阵链乘类似，不过这道题规定只能进行两次切割，所以子问题的数量实际上是减少了。 我在程序中编写的第一个循环用于第二次剪切，内部的嵌套循环用于第一次剪切。

伪代码草案和递归方程如下：

代码：

#include
using namespace std;
int main()
{
	string s1,s2;
	string s3,s4,s5;
	//string s6;
	string dp[55][55];
	for(int i=0;i<55;i++)
	{
		for(int j=0;j<55;j++)
		{
			dp[i][j]="{";  //赋初值 
		}
	}
	cin>>s1;
	int len=s1.size();
	for(int i=len-1;i>=2;i--)//从后往前循环  
	{
		s2=s1;
		s3=s2.substr(i,len-i); //切第二刀 
		reverse(s3.begin(),s3.end());
		for(int j=i-1;j>=1;j--)//从后往前循环 ，i最小是2，j最小是1，所以最终目标为dp[2][1] 
		{
			s4=s2.substr(j,i-j);//切第一刀 
			reverse(s4.begin(),s4.end());
			s5=s2.substr(0,j);
			reverse(s5.begin(),s5.end());
			dp[i][j]=min(s5+s4+s3,min(dp[i+1][j+1],min(dp[i][j+1],dp[i+1][j])));//递推方程 
		}
	}
	/*输出打印dp[][]表 
		for(int i=2;i