递归动态规划.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 38 行

#include<stdio.h>
#define m 5
int data[m][m]={
						{9},
						{12,15},
						{10,6,8},
						{2,18,9,5},
						{19,7,10,4,16}
					};
int dp[m][m];
int bigger(int a,int b)
{
	return a>b?a:b;
}
main()
{
	int answer(int,int);
	int max=answer(0,0);
	printf("%d",max);
	return 0;
}
int answer(int i,int j)
{
	if(dp[i][j])
	{
		return dp[i][j];
	}
	if(i==m-1)
	{
		dp[i][j]=data[i][j];
		return dp[i][j];
	}
	else
	{
		dp[i][j]=bigger(answer(i+1,j),answer(i+1,j+1))+data[i][j];
		return dp[i][j];
	}
}