知识点
LeetCode算法题
LeetCode算法题
复习
股票买卖系列(穷举+备忘录)
一次买入卖出
解题思路:
穷举思路。
1、两个for循环,穷举所有买卖可能,然后取差值最大的。
2、因为两个for相等于,固定buy的天数,然后穷举sell的天数,重复计算很多。因此,更好的穷举思路是:sell的天数肯定是从第1天开始(从第0天计算),因此完全可以通过一个变量存储[0..i]天的最小值,并随着天数更新,这样肯定差值最大。因此一个for循环即可搞定。
不限次数买入卖出
解题思路:
穷举思路:
因为不限制次数买入卖出,因此先利用一次买入卖出的来推导,发现会有无穷个for循环,因此肯定需要递归函数。递归函数参数为还剩下的天数,函数体中是一次买入卖出的穷举。
然后,可以利用固定sell来优化为一个for循环。
其次,穷举+备忘录。
基于上述的一个for循环的穷举,可以通过一个memo数组来去除重叠子问题(因为天数数组切片可以通过多条递归路径得到,因此有重叠子问题)。
最后,贪心算法。
该题目符合贪心条件,用贪心算法是最优解。核心思想就是全局最优解通过局部最优解得到,本题可以理解为:既然可以预知未来,那么能赚一点就赚一点
贪心算法解法为:
int process(int[] prices) { int res = 0; // 从第1天开始,只要能赚就立刻赚一点,汇总全部就是最优解 for (int i = 0; i < prices.length; i++) { if (prices[i] > prices[i - 1] res = res + (prices[i] - prices[i - 1]); } return res; }
限制交易次数
解题思路:
还是递归函数,不过参数多个k罢了。然后继续使用备忘录剪枝
含冷冻期
解题思路:
还是递归函数,参数还是只有天数数组。不过就是函数体中需要修改一下罢了。
含手续费
解题思路:
还是递归函数,参数还是只有天数数组。不过是利润中减去手续费罢了。
股票买卖系列(动态规划)
限制交易次数为k
解题思路:
该题目为股票买卖问题中最泛化的形式,通过该题目研究所有股票买卖问题。
首先,明确状态。状态有3个,天数、是否持有股票、还允许交易的次数。
然后,明确选择。选择有3个,买入、卖出、不操作。至于买入卖出的顺序等问题,可以先暂时忽略,这里只考虑选择。
用一个三维数组 dp 就可以装下这几种状态的全部组合,用 for 循环就能完成穷举。
明确dp数组定义。dp数组表示利润最大值。
根据状态和选择,找出状态转移方程:因为我们的选择是 buy, sell, rest,而这些选择是和「持有状态」相关的,所以只看状态转移的关键是持有状态。
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
最后,明确base case:
dp[-1][k][0] = 0; dp[-1][k][1] = -inf; dp[i][0][0] = 0; dp[i][0][1] = -inf
其他股票买卖
解题思路:
根据题意,直接套用上面的状态转移方程和base case
打家劫舍系列
基础打家劫舍
环形打家劫舍
解题思路:
第一间房子和最后一间房子也相当于是相邻的,不能同时抢,则有3种情况:1、首尾的都不抢;2、只抢头部;3、只抢尾部,这3种情况中最大的就是答案。
二叉树打家劫舍
解题思路:
还是打家劫舍解法,但是注意二叉树的左右节点都是相邻节点,因此结果为左右的相加。
1312.【让字符串成为回文串的最少插入次数】