在看fucking algorithm中的股票问题,记录以下get到的点
在定义dp数组时,dp[i][k][0,1]表示的是在第i天最多进行了k次交易,但是怎么表示这个最多的?(在我原先的考虑中是不是要把k当成到第i天已经进行了k次交易,然后求最多k次交易的最大收益时,按k从大到小进行遍历。当然最终的思想其实是一样的只是文中给出的方法更加精炼整体)
这个问题在定义base case中就考虑到了
dp[-1][k][0] = dp[i][0][0] = 0;
dp[-1][k][1] = dp[i][0][1] = -∞;
这里的dp[-1][k][0,1]就已经考虑到了k的余量,要做的还是填满这个dp表
网友评论