动态规划基础分析

动���规划的基本思想是是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中 得到原有问题的解。

分析是否可以用动态规划时，可以用小问题是否可以拓展到大问题中，

若可以，再从大问题到小问题分析动态规划思路。

具体还是要多做题，领悟动态规划。

---

 

买票股票

本题内容为在某一天买入，到某一天卖出（只购买一次），实现利益最大化 

从小问题到大问题分析

[7]：当天买当天卖，利润为0；

[7，1]：第二天卖即第一天买，第二天不操作即为第一天状态为[7]的情况（当天买当天卖）

[7,1,5]:  第3天卖即第2天买或第1天买，3不操作即为[7,1]的情况； 

可以发现从小问题中可以逐渐拓展到大问题里；可以考虑动态规划

大问题到小问题分析 

分析可以发现：第i天的情况可以分成以下几种情形：

状态转移方程 

先定义数组dp[ i ] [ j ]的含义：为在第 i 天持股状态为 j 的所有方案的最大利润

j=0 没持股；j=1 已持股。

price[ i ]为第i天股票价格，

#include #include  //maxusing namespace std;typedef long long ll;ll price[100005];//股票价格ll dp[100005][2];//0未持有，1持有，dp为利润int main(){    int n=0;    scanf("%d",&n);    for(int i=1;i