求解买股票问题实验报告（DP + LDS）

再次水一发题。。

一、 实验目的

1. 加深对最长公共子序列问题算法的理解，实现最长公共子序列问题的求解算法;
2. 通过本次试验掌握将算法转换为上机操作;
3. 加深对动态规划思想的理解，并利用其解决生活中的问题。

二、实验内容

任务：求解买股票问题

“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
"逢低吸纳,越低越买"这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。
以下面这个表为例, 某几天的股价是:
天数 ：1 2 3 4 5 6 7 8 9 10 11 12
股价 ：68 69 54 64 68 64 70 67 78 62 98 87

三、实验原理

首先本题就是求最长下降子序列的问题：巧妙利用动态规划思想

1. 原序列数组a
2. dp[i]代表前i个数的最长下降子序列长度
3. 动态维护一个dp[i]数组，若i位置之前j处有比当前大的数则更新当前为dp[i] = max(dp[i], dp[j] + 1);
4. 使用res来获得dp数组的最大值，即最终结果！

四、程序代码

解释：LDS函数为最长下降子序列函数，动态维护dp数组的值，返回dp中的最大值，为最终结果。
代码如下：

#include <iostream>

using namespace std; 

const int N = 1e6;
int a[N], dp[N], n;

int LDS()
{
    int res = 0;

    for(int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for(int j = 0; j < i; ++j)
            if(a[j] > a[i]) dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }
    return res;
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	cout << LDS() << endl; 
	return 0;
}

五、实验结果

测试一：

测试二：

六、分析总结

1. 动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
2. 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
3. 通过本次实验学习并了解掌握了最长下降子序列的求解，思路及解法，动态的维护一个数组，最终的最大值就是所求的答案。