4.动态规划
4.1 线性dp
还记得斐波那契数列吗？（是的，我又回来了）
可以用数组来记录前面斐波那契数列的值，以此推出后面的值。
| feb[0]=feb[1]=1; for(int i=2;i<=n;i++){ feb[i]=feb[i-1]+feb[i-2]; } |
这即是动态规划的思想：利用已有的结果以及递推方程来推出整体结果。
还有一种变种的线性dp，当数组中某个数选或不选对后面的结果都有影响时，那么可以把选或不选作为两种状态：
例如：求数组中取一些数要求取的数不能出现相邻，求取的数之和的最大值：
| int dp[200020][2]; //dp[i][0]代表不取第i个数的最大值，dp[i][1]则代表取其的最大值 for(int i=1;i<=n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]); //若不取a[i]，那么前一个数取不取都可以 dp[i][1]=dp[i-1][0]+a[i]; //取a[i]必须要求前一个数不能取 } cout<<max(dp[n][0],dp[n][1]); //最后要返回的是取/不取最后一个数-这两种情况 //的最大值 |
4.2 二维dp
和线性dp比，二维dp
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法笔面试宝典 文章被收录于专栏
算法笔面试真题解析
，可以适当对关键信息加粗一点，比如关键技术、性能指标之类的。