java动态规划

动态规划"/>

java动态规划

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1：
输入: prices = [7,1,5,3,6,4]
输出: 7
示例2：
输入: prices = [1,2,3,4,5]
输出: 4
思路：
采用动态规划的思路，每天只有持股或者未持股两种状态，因此可以new一个dp数组。
dp[i][0]:表示第i天未持股的利润，dp[i][1]:表示第i天持股的利润。
每天的状态只跟前一天相关，当天不持股的状态来自昨天不持股或者昨天持股，当天持股的状态来自昨天持股或者不持股，取最后一天不持股的状态就是问题的解。

代码：

    public int maxProfit(int[] prices) {int n=prices.length;int[][] dp = new int[n][2];dp[0][0] = 0;//表示第一天未持有股票的利润dp[0][1] = -prices[0];//表示第一天持有股票的利润for (int i = 1; i < n; i++) {//第i天未持股的利润dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);//第i天持股的利润dp[i][1] = Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);}return dp[n-1][0];}