求解问题类型：重叠子问题

两种写法:

递推：

#include 
     
      #include 
      
       using namespace std;const int maxn = 100;int dp[maxn] = { 0 };int f_seque(int n){	if (n == 1 || n == 2)		return 1;	if (n > 2)	{		if (dp[n] == 0)		{			dp[n] = f_seque(n - 1) + f_seque(n - 2);			return dp[n];		}		else return dp[n];	}}int main(){	int n = f_seque(3);	cout << n;	system("pause");	return 0;}
      
     

递推：

 

#include 
     
      #include 
      
       using namespace std;const int maxn = 100;int datas[maxn][maxn] = { 0 };int dp[maxn][maxn] = { 0 };int main(){    int n;    cin >> n;    for(int i=1;i<=n;++i)        for (int j = 1; j <=i; ++j)        {            int tem;            cin >> tem;            datas[i][j] = tem;        }    for (int i = 1; i <= n; ++i)        dp[n][i] = datas[n][i];    for(int i=n-1;i>=1;--i)        for (int j = 1; j <= i; ++j)        {            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + datas[i][j];        }    cout << dp[1][1];    system("pause");    return 0;}