动态规划解决股票交易与会议安排问题

"实验六 动态规划实验.pdf" 在本次实验中，我们主要探讨了两个动态规划的应用问题：买股票问题和会议安排问题。动态规划是一种优化技术，它通过将大问题分解为小问题的子集来求解，通常用于处理具有重叠子问题和最优子结构的问题。 1. 买股票问题 这是一个经典的动态规划问题，要求在满足股票价格逐次降低的情况下，找出最多能买几次股票。给定连续N天的股票价格，我们可以构建一个动态规划数组dp，其中dp[i]表示在第i天结束时最多能买多少次股票。状态转移方程为：dp[i] = max(dp[i-1], dp[j]+1)，其中j < i且股价满足股价[j] < 股价[i]。我们需要遍历所有可能的j，寻找这样的最大值。最后，dp[N-1]即为答案。这个问题的关键在于理解和构建正确的状态转移方程，以及识别如何利用之前的决策信息来优化当前的决策。 2. 会议安排问题 这个问题中，我们已经有了一个经过排序的订单列表，每个订单有开始时间和结束时间。dp数组表示在考虑前i个订单后，能够兼容的最大订单持续时间。pre数组记录了到达当前最大持续时间的前一个订单索引。为了找到一个兼容订单的最长序列，我们需要从最后一个订单开始回溯，根据pre数组的值来确定之前的选择。当pre[i]等于-1时，表示没有前一个订单与之兼容，此时应该停止回溯，即在横线处填写`break`。如果改为if(i==-1)作为判断条件，意味着我们直接检查当前索引是否等于数组长度减一，这样也可以达到同样的效果，因为数组下标从0开始，所以n-1表示最后一个元素，而pre[n-1]在本题中恰好是-1。 动态规划方法在解决这些问题中起到了关键作用，它通过自底向上的方式避免了重复计算，有效地提高了算法效率。在实际编程中，理解问题的动态规划模型，正确地定义状态和状态转移方程，以及有效地进行回溯或构建解决方案是至关重要的。 这两个问题展示了动态规划在解决实际问题中的灵活性和有效性，同时也提醒我们在处理复杂问题时，如何通过分解和组合找到问题的最优解。在学习和应用动态规划时，我们应该注重理解其背后的数学原理和逻辑，以便于解决更复杂的问题。