算法分析大作业

f[i][i][k] = (ch[i] == chars[k] ? 1: 0); /*

a = a*c || b*c || c*a b = a*a || a*b || b*b c = b*a || c*b || c*c */

for(int r=1; r

for(i=0; i

int j = i + r; //区间右端点 for(int k=i; k

f[i][j][0]

+=

f[i][k][0]*f[k+1][j][2]

f[i][k][1]*f[k+1][j][2] + f[i][k][2]*f[k+1][j][0]; f[i][j][1]

+=

f[i][k][0]*f[k+1][j][0]

f[i][k][0]*f[k+1][j][1] + f[i][k][1]*f[k+1][j][1]; f[i][j][2]

+=

f[i][k][1]*f[k+1][j][0]

f[i][k][2]*f[k+1][j][1] + f[i][k][2]*f[k+1][j][2]; } }

return f[0][n-1][0]; }

+

+

+

int main() {

ifstream fin(\ cout << \输入字符串：\ char ch[100];

fin >> ch; cout << ch; int n = strlen(ch);

cout << \结果为a的加括号方式为：\ fin.close(); return 0; }

1.5最终结果

2.动态规划解决汽车加油行驶问题

2.1问题描述

给定一个N*N的方形网络，设其左上角为起点○，坐标为(1，1)，X轴

向右为正，Y轴向下为正，每个方格边长为1。一辆汽车从起点○出发驶向右下角终点， 其坐标为（M，N）。在若干网格交叉点处，设置了油库，可供汽车在行驶途中，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：

（1）汽车只能沿网格边行驶，装满油后能行驶K条网格边。出发时汽车已装满油，在起点与终点处不设油库。

（2）当汽车行驶经过一条网格边时，若其X坐标或Y坐标减小，则应付费用B，否则免付费用。

（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。

（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费A）。 （5）（1）~（4）中的各数N，K，A，B，C均为正整数。

2.2算法设计思想

这个题目,应该说是刚开始的时候被他给吓到了，只是想着如何去把所有

的条件构造起来，然后使用网络流的方式来解决问题！但是，如果真的是很冷静下来好好地思考这道题目，就会发现如果没有那些限制条件，就是一个求解最长路的题目，这样就可以直接使用ＳＰＦＡ来解决这个问题！关键就是在于这个每次最多只能走Ｋ个网格边，这样就是限制了活动的范围，使得有的边无法扩展！因此可以考虑使用这个分层思想的最短路问题！就是通过将每一个点进行拆分，这样，就是相当于一种分类讨论的方式！而分类讨论

了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！关键点就是在于该如何选取变量来分层，这就是因情况而异了！像这道题目之中，就是通过油量的多少来扩展边的！分层思想，说穿了其实就是相当于这个动态规划之中的增加变量的方式来确定状态一样，他们的实质其实都是一样的！

2.3设计方法

采用的是动态规划的思想来解题,用备忘录的方法进行递归,递归的式子

后面写出.

不能直接以汽车行驶的费用为目标来进行动态规划,因为最优子结构性质得不到证明.

所以必须把油量和费用一起考虑,作为动态规划的对象,此时就有了最优子结构性质.

最优子结构性质的证明

证明:假设路径M是从起点◎到终点▲的一条最小费用路径,P(x,y)是M经过的一个点(非加油站),且油量和费用为(g,c),现假设有一条新路径Q从起点◎到点P(x,y),使得其在P(x,y)点的油量和费用为(g,c'),其中c'备忘录递归

刚开始的时候为每个网格点P(x,y)建立一个记录,初始化时,为该记录存入一个特殊值W,表示汽车未行驶过.那么在汽车行驶过程中,对每个待求的汽车最小费用值COST,先查看其相应的记录项C,如果存储的是初始值W,那么表示这个点P(x,y)是第一次遇到,此时计算出该点的最小费用值,并保存在其相应的记录项中,以备以后查看.若记录项C中存储的不是初始值W,那么表示该问题已经求解过了,其相应的记录项中存储的就是该点的最小费用值COST,此时要取出记录项C的值跟最新的计算出的COST进行比较,取其最小的那个数存入到C中.依此建立记录项C的值,当程序递归完成时,我们也得到了汽车行驶到(n,n)的最小费用值COST.

2.4源代码

#include \#include \