关于动态规划:这种动态规划你见过吗状态机动态规划之股票问题上

前言

在本篇文章当中次要通过介绍各种 股票问题 跟大家介绍 状态机动静布局 ，次要理解在 股票问题 当中是如何在动静布局当中进行状态转移的，通过认真分析状态转移过程给大家介绍 状态机动静布局。所谓状态机，就是有很多状态和他们之间的转移关系组成起来造成零碎，这个说法看起来有点高大上，其实很简略，在前面讲动静布局解法的时候大家就明确了。

交易股票的最佳时机 I

给定一个数组 prices，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。你只能抉择 某一天 买入这只股票，并抉择在将来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

输出：[7,1,5,3,6,4]

输入：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输出：prices = [7,6,4,3,1]

输入：0

解释：在这种状况下, 没有交易实现, 所以最大利润为 0。

暴力解法

在这个问题当中，咱们的工作是在某一天买入股票，而后在将来某天再将股票卖出去，那么咱们就能够用一个二重循环，第一层循环遍历每一天的股票，第二层循环遍历该天之后的股票，而后找到差值最大的那一天即可，也就是寻找某天前面价值最高的股票！通过做差失去差值，将差值最大的返回即可！

class Solution {public int maxProfit(int[] prices){
    int ans = 0;
    for (int i = 0; i < prices.length - 1; i++) {for (int j = i + 1; j < prices.length; j++) {ans = Math.max(ans, prices[j] - prices[i]);
      }
    }
    return ans;
  }

}

下面的代码的工夫复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，因为工夫简单度过高，下面的代码在 Leetcode 下面提交会超时。

贪婪解法

在暴力解法当中咱们思考的是寻找某天前面的最大值，在这个问题当中咱们能够换一个角度，就是寻找某天后面股票价值最低的那一天，而后在那一天买进，在当天卖出即可，这个成果和下面暴力解法是一样的。这样的话咱们能够用一个数组 mins 去存某一天后面价值最小的股票，而后做一个减法即可，即 prices[i] - mins[i]，这样咱们就失去了在第i 个地位卖出可能失去的最大的价值，那么咱们再比拟所有的这些值，咱们就能够找到最初的答案了！这样的话咱们能够将工夫复杂度升高到 $O(n)$。

class Solution {public int maxProfit(int[] prices) {
    int ans = 0;
    int[] mins = new int[prices.length];
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {min = Math.min(min, prices[i]);
      mins[i] = min;
    }
    for (int i = 0; i < prices.length; i++) {ans = Math.max(ans, prices[i] - mins[i]);
    }
    return ans;
  }
}

下面的代码的工夫复杂度为 $O(n)$，空间复杂度也是 $O(n)$，其实认真思考一下咱们还能够升高空间复杂度：

class Solution {public int maxProfit(int[] prices) {
    int low = Integer.MAX_VALUE;
    int ans = 0;
    for (int i = 0; i < prices.length; i++) {low = Math.min(prices[i], low);
      ans = Math.max(ans, prices[i] - low);
    }
    return ans;
  }
}

咱们在第一次遍历的时候能够用一个值 low 保留第 i 个地位右边最小的值即可，并且在遍历的过程当中不断更新 low 值，而且咱们在遍历的时候能够顺便求出对应地位的可能获取的最大价值，能够防止第二次遍历。在这个状况下咱们的工夫复杂度为 $O(n)$，空间复杂度为 $O(1)$。

动静布局解法

在求解动静布局问题的时候通常的步骤有以下几个：

• 寻找可能示意状态的数组 dp，即咱们须要寻找dp 的含意，剖析须要用几纬数组示意具体的状态。
• 通过剖析问题，寻找动静转移公式。
• 初始化状态数组。
• 通过剖析动静转移方程，确定数组的遍历程序。

状态示意数组

在这个问题当中咱们用一个二维数组去示意咱们的状态，在这个问题当中次要有两个状态，一个是手上有股票，另一是手上没有股票：

• dp[i][0]示意在第 i 天手上没有股票可能取得的最大的收益，比方咱们在第一天的没有股票的收益为 0 元。
• dp[i][1]示意在第 i 天手上存在股票可能取得的最大的收益，比方咱们在第一天买入股票之后收益为-prices[0]。

那么咱们最初的答案是dp[N][0]，这个示意在最初一天，咱们的手中不存在股票，即咱们将股票卖出去可能获取的最大的收益。

状态转移方程

当初咱们来剖析一下如何进行状态的转移：

• dp[i][0]的状态如何从第 i-1 的状态转移过去：

  • 如果第 i-1 个状态是手中不存在股票，即 dp[i-1][0]，那么第i 个状态也没有股票，那么间接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
  • 如果第 i-1 个状态手中存在股票，即 dp[i-1][1]，那么如果想在第i 个状态没有股票，那么就须要将股票卖出，那么收益就为dp[i-1][1] +prices[i]，即dp[i][0] = dp[i-1][1] +prices[i]。
  • 综合下面的两种转移形式能够失去上面的转移方程：

  $$
  dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i])
  $$

• dp[i][1]的状态如何进行转移：

  • 如果第 i-1 个状态是手中不存在股票，即 dp[i-1][0]，而第i 个状态有股票，那么 dp[i][0] = -prices[i]，因为买入股票，而且只可能买入一次，因而间接等于-prices[i] 即可，留神这里不能是 dp[i - 1][0] - prices[i]，因为在dp[i-][0] 当中可能存在先买入再卖出的状况，而题干要求只能买入卖出一次。
  • 如果第 i-1 个状态手中存在股票，即 dp[i-1][1]，而第i 个状态有股票，因而不须要进行交易，即dp[i][1]=dp[i - 1][1]。
  • 综合下面的两种转移形式能够失去上面的转移方程：

  $$
  dp[i][1] = max(dp[i – 1][1], -prices[i]);
  $$

  整个状态转移过程如下图所示：

下面所谈到的有两种状态，一种是有股票，一种是没有股票，这两种状态须要从第 i-1 行转移到第 i 行，即从第 i-1 行的有股票和无股票状态转移到第 i 行的有股票和无股票状态，这就是咱们在前文谈到的状态机，咱们曾经有了状态（是否持有股票），而且也有了状态之间的转换，这就是 状态机动静布局 。你可能会问这如同跟之前传统的动静布局区别也不是太大啊，这是因为在这个问题当中只有两个状态，咱们在下篇当中遇到的问题就会有多个状态了，在那个时候你可能就更加了解为什么称这种动静布局叫做 状态机动静布局 了。

• 综合两种状态，整个转移形式如下：

$$
\begin{cases}dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i])\\
dp[i][1] = max(dp[i – 1][1], -prices[i]);
\end{cases}
$$

整个代码如下：

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][2];
    // 初始化数组 dp[0][0] 默认等于 0 不必
    // 显示初始化
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; 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[prices.length - 1][0];
  }
}

数组优化（滚动数组优化）

咱们能够仔细分析一下下面的状态转移方程，能够发现第 i 行，只依赖第 i-1 行，因而咱们只应用两行数组即可，第一行揣测出第二行，第二行揣测进去的后果再存回第一行 …….

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[2][2];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; i++) {dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);
      dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], -prices[i]);
    }
    return dp[(prices.length - 1) % 2][0];
  }
}

能够应用位运算略微优化一下（上面代码优化的依赖原理：$a \& (2^n – 1) = a \% 2^n$）：

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[2][2];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; i++) {dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
      dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], -prices[i]);
    }
    return dp[(prices.length - 1) & 1][0];
  }
}

最终通过下面的优化动静布局的工夫和空间复杂度能够优化到 $O(n)$ 和 $O(1)$。

小结

在上文当中次要介绍了 交易股票的最佳时机 I 各种解决办法，其中最次要想介绍的就是动静布局的办法了，而在动静布局当中最重要的就是状态之间如何进行转换，这个题中其实很像状态机中的状态转换，在这个问题当中只有两种状态之间的转换——有股票和没股票，大家如果要弄明确 状态机动静布局 算法，那就须要粗浅的去了解下面状态转换的过程。

交易股票的最佳时机 II

给你一个整数数组 prices，其中 prices[i] 示意某支股票第 i 天的价格。在每一天，你能够决定是否购买和 / 或发售股票。你在任何时候 最多 只能持有 一股 股票。你也能够先购买，而后在 同一天 发售。返回你能取得的最大 利润。

示例 1:

输出：prices = [7,1,5,3,6,4]

输入：7

解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 – 1 = 4。

随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6 - 3 = 3。总利润为 4 + 3 = 7。

示例 2：

输出：prices = [1,2,3,4,5]

输入：4

解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 – 1 = 4。

总利润为 4。

这道题和第一题的区别就是，在这道题当中你能够交易股票屡次，然而最多只能持有一只股票，因而这道题和第一题的大多数状况是雷同的。

状态示意数组

在这个问题当中咱们用一个二维数组去示意咱们的状态，在这个问题当中次要有两个状态，一个是手上有股票，另一是手上没有股票：

• dp[i][0]示意在第 i 天手上没有股票可能取得的最大的收益，比方咱们在第一天的没有股票的收益为 0 元。
• dp[i][1]示意在第 i 天手上存在股票可能取得的最大的收益，比方咱们在第一天买入股票之后收益为-prices[0]。

那么咱们最初的答案是dp[N][0]，这个示意在最初一天，咱们的手中不存在股票，即咱们将股票卖出去可能获取的最大的收益。

状态转移方程

当初咱们来剖析一下如何进行状态的转移：

• dp[i][0]的状态如何从第 i-1 的状态转移过去：

  • 如果第 i-1 个状态是手中不存在股票，即 dp[i-1][0]，那么第i 个状态也没有股票，那么间接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
  • 如果第 i-1 个状态手中存在股票，即 dp[i-1][1]，那么如果想在第i 个状态没有股票，那么就须要将股票卖出，那么收益就为dp[i-1][1] +prices[i]，即dp[i][0] = dp[i-1][1] +prices[i]。
  • 综合下面的两种转移形式能够失去上面的转移方程：

  $$
  dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i])
  $$

• dp[i][1]的状态如何进行转移：

  • 如果第 i-1 个状态是手中不存在股票，即 dp[i-1][0]，而第i 个状态有股票，这道题目和上一道题目只有这个中央是不统一的，在上一道题当中 dp[i][0] = -prices[i]，这是因为只可能买入股票一次，具体起因是在dp[i - 1][0] 当中能够存在股票买入，而且曾经卖出这种状况，而第一题只能买入卖出一次，而在这道题目当中，可能交易股票屡次，因而dp[i][0] = dp[i - 1][0] - prices[i]。
  • 如果第 i-1 个状态手中存在股票，即 dp[i-1][1]，而第i 个状态有股票，因而不须要进行交易，即dp[i][1]=dp[i - 1][1]。
  • 综合下面的两种转移形式能够失去上面的转移方程：

  $$
  dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);
  $$

• 综合下面的两个状态：

$$
\begin{cases}dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i])\\
dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);
\end{cases}
$$

参考代码如下：

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[2][2];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; i++) {dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
      dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
    }
    return dp[(prices.length - 1) & 1][0];
  }
}

贪婪解法

因为咱们能够无数次买入卖出，因而只有存在前一天的价格低于明天的价格，那么咱们就能够在前一天买入，在明天卖出，在这种状况下咱们的收益就是最大的，因为咱们抓住了“每一次赚钱的机会”。

• 比方prices=[1, 2, 3]，咱们的收益就等于(2 - 1) + (3 - 2) = 2，这个过程相当于在第一天买入，第二天卖出，第二天再买入（留神题目当中阐明了一天能够同时买入和卖出，只须要保障手上的股票不超过两个），第三天卖出。
• 又比方prices=[4, 5, 3, 6]，咱们的收益等于(5 - 4) + 0 + (6 - 3) = 4，这个过程相当于第一天买入第二天卖出，第三天再买入第四天卖出。

代码如下：

class Solution {public int maxProfit(int[] prices) {
    int ans = 0;
    int n = prices.length;
    for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
  }
}

总结

在本篇文章当中次要给大家介绍了两个股票问题，这两个问题比拟中规中矩的办法就是应用动静布局，然而也能够应用贪婪法奇妙求解。在本文当中最想跟大家介绍的还是 状态之间的转换，然而在本文当中的两个问题当中波及的状态还是比拟少，只有含有股票和不含有股票两种状态，然而也能够看作状态机当中状态之间的转换。下篇当中的题目状态会略微多一点，可能大家了解起来更加容易一点！

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。