在动态规划问题中，我们经常会遇到以下问题，最优解倒是求出来了，但是最优解的路径呢？如何输出？这确实是一个问题，而且往往比较难哟。。
我这里说的路径是指，像在钢条切割问题中，从哪些地方切可以达到最优化，在矩阵链乘问题中，从哪些地方进行组合可以使效率最高？
在钢条切割问题中：
for(j=1;j<=i; j++){ if(priceStore[i-j]+ironPrice[j-1]>price){ pathStore[i]=j; //意思为使是长度为i的钢条价格达到最优，需要从第j个位置进行截断，当然 //可能还有其它的位置呢。 }
while(n>0){ std::cout<<pathStore[n]<<std::endl; n=n-pathStore[n]; } 在以上问题中，由于我们只要记住切割点就可以了，因为钢条的价格只与它的长度有关，与位置无关，因此可以说是一个一维的问题。 于是只要用一个一维的数组记录就可以了，也就是用数组的下标表示为钢条的长度，而该位置数组的值表示为切割的位置 ，如下
pathStore[i]=j表示对于长度为i的钢条的它的最优解是从位置j进行切割。
其实我们要明白一点，那就是我们的每次迭代都只产生一次切割。
for(int i=1;i<=Length; i++){
price=Max((ironPrice[i]+ironCutPrb(ironPrice,Length-i-1)),price);
}
在上面的程序中，其实如果在“归”到最后的时候，上面只产生了一次切割，也就是从i=1到i<=Length,我们只切割一次。只需记录一次就可以了。
然后每次子问题的迭代都会记录一次这些问题。
while(n>0){
std::cout<<pathStore[n]<<std::endl;
n=n-pathStore[n];
}
这个就是输出代码啰。。你看，首们我们n被初使化成了Length，实参。于是第一次会打印当长度为Length时的切割位置，也就是从哪里切割。然后进入到子问
题所记录的切割点。这里我人还剩下多少呢？n-pathStore[n]，这就是我们的第一个子问题所要处理的长度，于是有人问，难道pathStore[n]就不需要处理了吗？
其实我们的代码是这么写的，在主代码中，
for(int i=1;i<=Length; i++){
price=Max((ironPrice[i]+ironCutPrb(ironPrice,Length-i-1)),price);
}
我们是固定左边，也就是左边不切割，只切割右边。当然我们也就只记录右边的点啰。
在矩阵链乘法的问题中，
if
(
multiCount
>(
multiplay_iterator
(
multiDem
,
start
,
i
)+
multiplay_iterator
(
multiDem
,
i
+
1
,
end
)+
multiDem
[
start
-
1
]*
multiDem
[
i
]*
multiDem
[
end
])){
storePath[start][end]=i;
multiCount=multiplay_iterator(multiDem,start,i)+multiplay_iterator(multiDem,i+1,end)+multiDem[start-1]*multiDem[i]*multiDem[end];
}
void
printMultiPath
(
int
start
,
int
end
){
if(start==end)
return ;
if(storePath[start][end]==start||storePath[start][end]==end)
return;
std::cout<<"A"<<start<<" * "<<"A"<<storePath[start][end]<<std::endl;
std::cout<<"A"<<storePath[start][end]+1<<" * "<<"A"<<end<<std::endl;
printMultiPath(start,storePath[start][end]);
printMultiPath(storePath[start][end]+1,end);
}
我们有处理这个问题用了一个二维数组，因为这种情况和位置有关呢，其行和列分别表示start和end。
int storePath[20][20]={0};
不同于钢条只与长度有关。而且输出该组合也用了递归的思想。原问题->子问题->子子问题->.....->子....子问题。。。
printMultiPath(start,storePath[start][end]);
printMultiPath(storePath[start][end]+1,end);
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655541.html
