线性dp：LeetCode122.交易股票的最佳时机ll
交易股票[*]本文所讲解的内容与LeetCode122. 交易股票的最佳时机ll，这道题题意相同，阅读完本文后可以自行挑战一下
[*]力扣链接
题目叙述：
给定一个长度为N的数组，数组中的第i个数字表示一个给定股票在第i天的价格。
筹划一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次交易一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉悠前的股票)。一次买入卖出合为一笔交易。
输入格式：
第一行包含整数 N，表示天数。第二行包含N个不大于10000的正整数表示天天股票的价格。
输出格式
输出一个整数，表示最大利润。
输入样例1
6
7 1 5 3 4 6输出样例1
7输入样例2
5
7 6 4 3 1输出样例2
0样例表明：
[*]样例1:在第2天买入，在第3天卖出，这笔交易所能获得利润=5-1=4。随后在第4天买入，在第6天卖出,这笔交易所能获得利润=6-3=3。共得利润4+3 =7
[*]样例2:在这种情况下,不举行任何交易，所以最大利润为 0。
动态规划思路讲解：
[*]我们分析总利润可知，总利润是关于天数i 的函数，并且在第i天的时候，只有两种状态与之对应
[*]1.手中无票：dp
[*]2.手中有票：dp
[*]所以说我们可以设置dp,dp 为状态变量，然后举行状态的转移，最终得出我们需要的答案。
1.状态变量的含义
[*]dp表示第i天，手中无票时能够获取的最大利润
[*]dp表示第i天，手中有票时能够获取的最大利润
2. 递推公式
[*]我们可以使用带权的有向图来生动的理解这个过程，我们要知道递推公式，就要了解状态转移的那个过程，也就是我们当前的状态是由以前的哪些状态推导而来。
[*]
[*]dp表示第i天，手中无票时能获取的最大利润，我们可以通过dp 和dp ，也就是第i-1天，手中有票大概手中无票这两个状态推导而来，如果是第i-1天手中无票，那么表示没有发生交易，那么dp=dp ，反之，从i-1天有票到第i天无票，那么意味着我们在第i天卖掉了股票，此时dp=dp+w ，由于我们是取最大利润，所以说是取二者的最大值，即：
dp=max(dp,dp+w);
[*]
[*]dp 也是同理，跟上面的推导方式差不多，所以我就不在赘述了
dp=max(dp,dp-w);
[*]所以说，总的递推公式如下：
dp=max(dp,dp+w);
dp=max(dp,dp-w);3.如何初始化？
[*]我们由这个递推公式，如何初始化边界条件呢？
[*]假设我们从第1天开始，到第n天结束，那么我们第一天的两个状态就是边界条件
dp=0; //第1天无票的最大利润就是0
dp=-w;//第1天就有票证明我买了第一天的那个股票4. 遍历顺序
[*]由递推公式可知，我们的状态变量dp,dp取决于dp,dp。所以说我们的遍历顺序是从前到后举行遍历。
5. 举例打印dp数组
[*]在本题，读者可以自行在for循环内举行插入printf语句举行验证我们dp数组的正确性
代码：
#include#includeusing namespace std;const int N = 100010;int w,dp;int n;int main(){scanf("%d", &n);for(int i=1;i
页:
[1]