四、动态规划

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]);      //最后要返回的是取/不取最后一个数-这两种情况
//