做网站的哪里好,建设网站怎么提需求,爱站网在线全集私人影视,汕头网页制作本题之前采用贪心算法来解决#xff0c;现在可以采用动态规划来解决#xff0c;通过dp数组记录每次的状态从而获取到最大的利润。
这里dp数组定义为二维数组 dp[price.length][2]#xff0c;其中price.length表示第i天#xff0c;[2]其中有0/1两种状态#xff0c;[0]表示… 本题之前采用贪心算法来解决现在可以采用动态规划来解决通过dp数组记录每次的状态从而获取到最大的利润。
这里dp数组定义为二维数组 dp[price.length][2]其中price.length表示第i天[2]其中有0/1两种状态[0]表示持有股票[1]表示没有持有股票。注意持有并不代表一定是当天买入也可能是之前买入的。
那么dp[i][0]表示第i天持有股票那么i-1天可能持有股票此时是dp[i-1][0]如果第i-1天没有持有股票那一定是第i天买入的第i天买入股票由于开始的时候手里没有钱当买入的时候手里的金额是-price[i]。所以 持有股票的递推公式dp[i][0] Math.max(dp[i-1][0]-price[i])。如果第i天不持有就是dp[i][1] 第i天不持有的话可能是i-1天就不持有了那么就是dp[i-1][1]也可能是第i天卖掉了那么就是dp[i-1][0]price[i]。所以递推公式就是dp[i][1] Math.max(dp[i-1][1]dp[i-1][0]prices[i])。
初始化dp[0][0]表示第0天持有股票那么一定是当天买入的股票所以此时是-price[0]。dp[0][1]表示第0天不持有股票则一定是0.
遍历顺序我们是根据前一天的状态得到后一天的状态所以i从1开始直接遍历。
打印数组
class Solution {public int maxProfit(int[] prices) {if (prices null || prices.length 0) return 0;int length prices.length;// dp[i][0]代表第i天持有股票的最大收益// dp[i][1]代表第i天不持有股票的最大收益int[][] dp new int[length][2];int result 0;dp[0][0] -prices[0];dp[0][1] 0;for (int i 1; i length; i) {dp[i][0] Math.max(dp[i - 1][0], -prices[i]);dp[i][1] Math.max(dp[i - 1][0] prices[i], dp[i - 1][1]);}return dp[length - 1][1];}
}
