文本串最优分行方案程序编写(C++)

题目如下:列表并至少给出4步典型过程,求文本串"Do you like those people who always think of money and cannot remember the past."在列宽为15,惩罚函数为行空余空间的平方(最后一行不计惩罚)时的最优分行方案.
谢谢一楼的朋友哈，能否把算法设计的思路说一下，再把程序的注释加一下，50分奉上，非常感谢！！

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

#define SQRE(a) (a)*(a)
const int infinity=6553;
const int exce=-2;

const int lineWidth=15;
string ori("Do you like those people who always think \
of money and cannot remember the past. ");
//char ori[]="hello world ";
//char ori[]="aaa bb ccc ";
vector<string> index;
int* fun;
int** c;
int* funChoose;

void initial()
{
fun=new int [index.size()+1];
funChoose=new int [index.size()+1];

c=new int* [lineWidth+1];
for (int i=0;i<lineWidth+1;i++)
{
c[i]=new int [lineWidth+1];
for (int j=0;j<lineWidth+1;j++)
{
c[i][j]=exce;
}
}

for (int i=0;i<index.size()+1;i++)
{
fun[i]=exce;
funChoose[i]=exce;
}
}

void debugPrint()
{
cout<<"**************\n";
cout<<"function return:\n";
for(int i=0;i<16;i++)
{
cout<<setw(5)<<fun[i]<<" ";
}
cout<<"\n**************\n";
cout<<"function choose:\n";
for(int i=0;i<16;i++)
{
cout<<setw(5)<<funChoose[i]<<" ";
}
cout<<"\ncost(i,j)"<<endl;
for(int i=0;i<lineWidth;i++)
{
for (int j=0;j<lineWidth;j++)
{
cout<<setw(5)<<c[i][j];
}
cout<<"\n";
}
}

void split()
{
string tmp="";
for (int i=0;i<ori.length();i++)//sizeof 是否有效？
{
if (ori[i]==' ')
{
index.push_back(tmp);
tmp.clear();
}
else
tmp=tmp+ori[i];
}
}

int cost(int i,int j)
{
int val=infinity;
int len=0;
if (i>j)
{
cerr<<"Error:i>j!";
return exce;
}

if (c[i][j]!=exce)
return c[i][j];
else
{
for(int k=i;k<j;k++)
{
len+=index[k].length();
}
len+=j-i-1; //space count
if (len>lineWidth)
{
c[i][j-1]=infinity;
return infinity;
}
else
{
c[i][j-1]=SQRE(lineWidth-len);
return SQRE(lineWidth-len);
}
}
}

int f(int j)
{
int min=65535;
if (fun[j]!=exce)
return fun[j];
else
{
if (cost(0,j)==infinity)
{
for (int k=1;k<j;k++)
{
if (min>f(k)+cost(k,j))
{
min=f(k)+cost(k,j);
funChoose[j]=k;
}
}
}
else
{
min=cost(0,j);
}

fun[j]=min;
return min;
}
}

void print()
{
vector<int> stack;
int size=lineWidth;
for (int i=0;i<lineWidth;i++) //print the line width
{
cout<<"*";
}
cout<<endl;
stack.push_back(size);
while(funChoose[size]!=exce)
{
stack.push_back(funChoose[size]);
size=funChoose[size];
}
stack.push_back(0);//begin

for (int i=stack.size();i>1;i--) //print the plain text
{
for(int j=stack[i-1];j<stack[i-2];j++)
{
cout<<index[j]<<" ";
}
cout<<endl;
}
}

int main()
{
split();
initial();
cout<<f(index.size())<<endl;
print();
return 0;
}

采用动态规划的方法完成，至于四步典型过程，着实没有想出来。。。
一般是写惩罚函数、写递归式、完成递归实现，完成从底向上的算法吧

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息