最简单和经典的一维和线性dp：
斐波那契和连续最大和问题：
把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1，把问题转化为规模缩小了的同类问题的子问题 2，有明确的不需要继续进行递归的条件(base case) 3，有当得到了子问题的结果之后的决策过程 4，不记录每一个子问题的解。
而我们需要把这种递归思路转换为动态规划
递归到动规的一般转化方法
1 递归函数有n个参数，就定义一个n维的数组
2 数组的下标是递归函数参数的取值范围
3 数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。
1. 将原问题分解为子问题
把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决 子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。
2.确定状态 整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。
3.确定一些初始状态（边界状态）的值
4. 确定状态转移方程
定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。
//斐波那契 class Solution { public: int Fibonacci(int n) { if(n==0) return 0; if(n==1||n==2) return 1; int first=1,second=1; for(int i=2;i<n;i++) { int temp=second; second=first+second; first=temp; } return second; } }; //连续最大和 #include <iostream> #include <vector> using namespace std; int fun(vector<int> & v) { int max=v[0]; int ret=max; for(int i=1;i<v.size();i++) { max=std::max(max,0)+v[i]; ret=std::max(ret,max); } return ret; } int main() { int n; while(cin>>n) { vector<int> v; v.reserve(n); while(n--) { int num; cin>>num; v.push_back(num); } cout<<fun(v)<<endl; } }
