[数据结构与算法]acm算法之动态规划 dp思想

/*此处为dp动态规划求解和为n的数，乘积最大问题

 用动态规划的时候   不可能在子问题还没有得到最优解的情况下就做出决策，
 而是必须等待  子问题得到了最优解之后才对当下的情况做出决策，
 所以往往动态规划都可以用 一个或多个递归式来描述
一般遇到一个动态规划类型的问题，都先要确定最优子结构，还有重叠子问题，这两个是动态规划最大的特征，然后就是要写 动态规划的状态方程
记忆化搜索是倒做的“递归式动态规划”

动态规划的核心：状态与状态转移方程(csdn中收藏了许多动态规划方程样式)

在DP中被称为状态的定义，其中子问题被称为状态。
对于问题2:，如何从子问题到原问题，在DP被称为状态转移方程。*/ 

#include <bits/stdc++.h>
using namespace std;
const int N=5e3;
int a[N];
long long fib(int n)
{
	int i , j , t;
			for(i=2;i<=n;i++)//注意到是从2开始的  自下而上的求解，得到每一个a[n]的值，再返回最终结果 
			{
			
			for(j=1;j<i;j++)
			{
				t=max(j*(i-j),j*a[i-j]);
				a[i]=max(t,a[i]);
				
			}
	}
		return a[n];
	
 } 
int main(void)
{
	int n;
	memset(a,-1,sizeof(a));
	a[1]=1;
	cin>>n;
	cout<<fib(n)<<endl;
}