阅读下面一段程序： [cpp] view plain cop

[问答题]

阅读下面一段程序：

[cpp] view plain copy

int foo(int x , int y) {

if(x == 0 || y == 0)

return 2;

return foo(x - 1 , y ) + foo(x , y - 1);

}

（ 1 ）当输入的 x 和 y 分别为 8 和 8 时，写出该程序的结果，并写出你的演算过程。
（ 2 ）该程序的执行效率很低，请写出你能想到的更高效 f 函数的实现方法。

guanq

//思路也很简单，很编辑距离问题几乎一样，动态规划可以很容易求出，时间复杂度为O(x*y)
int foo(int x,int y)
{
	int **a=new int *[x+1];
	int i=0,j=0;
	for(i=0;i<=x;i++)
		a[i]=new int[y+1];
	for(i=0;i<=x;i++)
		a[i][0]=2;
	for(i=0;i<=y;i++)
		a[0][i]=2;
	for(i=1;i<=x;i++)
	{
		for(j=1;j<=y;j++)
		{
			a[i][j]=a[i-1][j]+a[i][j-1];
		}
	}
	return a[x][y];
}

发表于 2017-02-18 10:08:32 回复(0)