Leetcode 121 动态规划（原名字不通过审核）

难度：简单
频率：145
题目：
给定一个数组prices，它的第i个元素prices[i]表示一只给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

解题方法：动态规划、暴力解法[两遍循环]

• 动态规划用于多阶段决策问题；
• 动态规划问题的问法：只问最优解，不问具体解；
• 掌握无后效性解决动态规划问题：把约束条件设置成为状态。

解题思路：
1.题目只问最大利润，没有问这几天具体哪一天买，哪一天卖。 也就是只问 最优解，不问具体解。
2.找出约束条件【无后效性】：

• 条件①：你不能在买股票前卖出股票。
• 条件②：最多只允许完成一笔交易。

因此当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把是否持股涉及到状态数组中。

状态定义：
dp[i][j]:下表为i这一天结束时，持股状态为j时，我们持有的现金数。

• j=0,表示当前不持股。
• j=1,表示当前持股。

推导状态转移方程：
dp[i][0]:规定今天不持股，有以下两种情况：

• 昨天不持股，今天什么都不做；
• 昨天持股，今天卖出（现金增加）；
  dp[i][1]:规定今天持股，有以下两种情况
• 昨天持股，今天什么都不做；
• 昨天不持股，今天买入（手上的现金时当天股价的反数）

public class Solution {public int maxProfit(int[] prices) {int len=prices.length;if(len<2){return 0;}int [][] dp=new int[len][2];dp[0][0]=0;dp[0][1]=-prices[0];//从第二天开始遍历for(int i=1;i<len;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=Math.max(dp[i-1][1],-prices[i]);}return dp[len-1][0];} }

重点注意的地方：

• 首先判断是否适合动态规划

  • 特征1：只求最值，不求具体值。
  • 特征2：多阶段决策，每天都能做决定【0 or 1】

• 状态方程很重要

  • 状态转移方程里需要考虑无后效性，即约束条件，例如买股票只能买卖一次、卖只能在卖后面。
  • dp[i][x]

• 遍历是从第二天开始，因为状态转移方程的每一天都跟前一天有关，i=0，则i-1会变成负数。

• 二维数组 int[len][2]

• 返回值为最后一天没持股的金额

总结

以上是生活随笔为你收集整理的Leetcode 121 动态规划（原名字不通过审核）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。