DP（动态规划）：
概念： 用来解决一类最优化问题的算法思想，即 将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解得到原问题的最优解，DP会将每个求解过程的自问题的解记录下来，下次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算
总之：一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决
2.动态规划的递归写法
//斐波那契数列为例 int f(int n){ if(n==0||n==1) return 1; else return f(n-1)+f(n-2); } /*这个递归会涉及到很多重复的计算，比如n==5时，f(5)=f(4)+f(3),接下来计算f(4)时会有 f(4)=f(3)+f(2),所以f(3)会被重复计算，实际复杂度为O(2^n) 为了避免重复计算，开一个一维数组dp保存已经计算过的结果，dp[n]记录f(n)的结果 dp[n]=-1表示没有被计算过*/ int f(int n){ if(n==0||n==1) return 1; if(dp[n]!=-1) return dp[n];//说明已经计算过，直接返回结果，无需重复计算 else{ dp[n]=f(n-1)+f(n-2); return dp[n]; } } //复杂度降到了O(n)