By

文章目录
  1. 1. 什么样的问题适合用DP来解决
  2. 2. 使用DP来解决问题的特征
  3. 3. DP问题思考和解决的过程是怎样的
  4. 4. DP问题的程序模版是怎样的
  5. 5. 一些适合DP的经典问题
    1. 5.1. Fibonacci 数列
  6. 6. 爬楼梯问题
  7. 7. 换硬币
  8. 8. 三角形最小路径和
  9. 9. 乘积最大子序列
  10. 10. 最长递增子序列问题（Longest Increasing Subsequence）
  11. 11. 编辑距离（Edit Distance/Levinstein Distance）
  12. 12. 买股票系列问题
    1. 12.1. 最简单的买股票时机问题
    2. 12.2. 同一股票可以交易无数次（买之前需要将之前买进的股票卖出）
    3. 12.3. 交易两次，不能同时拥有两只股票
    4. 12.4. 交易K笔，不能同时拥有两只股票
    5. 12.5. 交易有冻结期
    6. 12.6. 交易有手续费

动态规划(Dynamic Programming 简称 DP)是一类优化问题的总称，单从名称上来看，其实这里的programming并不是程序编程的意思，至于为什么要叫这个名字，只能说是算法界的一个历史原因，详情请查看Why is dynamic programming called dynamic programming?。

什么样的问题适合用DP来解决

DP的确是和一般算法和递归问题有特殊的特征，因此需要拿当前的问题和DP的问题解法套用。
解决DP问题的关键是定义合适的状态，如果定义正确的状态那么DP问题就解决了一半。

使用DP来解决问题的特征

能使用DP解决的问题具备下面3个特征

  1. 最优子结构：如果最优解的所有子问题的解也是最优的，那么就称这个问题具有最优子结构。
  2. 无后效性：也就是后面的状态一旦确定就不会影响之前决策过的状态。
  3. 有重复子问题：分拆的子问题之间不独立。

更多详细内容参照这里

DP问题思考和解决的过程是怎样的

  1. 递推
  2. 状态的定义
  3. 最优子结构
  4. 状态转移方程（DP方程）

DP问题的程序模版是怎样的

为了描述方便这里用一维DP问题为例，二维、三维问题类似： 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int solveDynamicProgrammingProblem(int problemSize) {
    // 定义状态，生成DP数组
    int[] dp = new int[problemSize];
    // 根据实际情况，初始化DP数组的初始值
    dp[0] = ...

    // 这里k代表DP数组初始值后的第一个整数
    for (int i = k; i < problemSize; i++) {
        dp[i] = _optimizedSubStructureFunction(i);
    }

    return dp[problemSize];
}

好的，现在我们有了锤子，就可以找钉子了。

一些适合DP的经典问题

Fibonacci 数列

问题描述：
原题传送门

问题： 求Fibonacci数列的第n项值。
分析后知道由于Fibonacci数列定义的性质，我们有该问题是有递推的结构，并且状态转移方程其实就是数列的定义：$$f(n) = f(n - 1) + f(n - 2)$$

下面我们就用DP的方式来解fibonacci数列问题：

1
2
3
4
5
6
7
8
9
10
11
  public long fibonacci(int n) {
    if (n == 0) return 0;
    if (n < 3) return 1;
    long[] fibArray = new long[n + 1];
    fibArray[1] = 1;
    fibArray[2] = 1;
  for (int i = 3; i <= n; i++) {
    fibArray[i] = fibArray[i - 1] + fibArray[i -2];
  }
  return fibArray[n];
}

下面做下复杂度分析：
首先是时间复杂度： DP的算法使用到了一个n-2的循环， 并且循环内部的计算结果使用了上面子问题的缓存，因此这个循环的复杂度是$O(n)$
其次是空间复杂度： DP的算法使用了额外的长度为n的数组因此空间复杂度为$O(n)$

这里使用了$O(n)$的额外空间，我们能否在空间上在寻找一个优化？答案是肯定的。 

1
2
3
4
5
6
7
8
9
10
11
12
public long fibonacci(int n) {
  if (n < 2) return 1;
  long first = 1;
  long second = 1;
  for (int i = 3; i <= n; i++) {
    long third = first + second;
    first = second;
    second = third;
  }

  return second;
}

好吧， 我们现在有了时间复杂度：$O(n)$, 空间复杂度$O(1)$的算法实现，抛开动态规划这个前提，就这个问题本身来说还有其他更好的解决方案么？ 答案是肯定的：

斐波那契数列其实在数学上是有一个通项公式的：
$$
f(n) = \frac{(\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n}}{\sqrt{5}}
$$
这里可以通过这个数学上的通项公式求出结果，至于算法复杂度，因为过程中使用了n次幂的数学计算，这个计算的时间复杂度会是$O(log^n)$的，所以整个的时间复杂度会是$O(log^n)$

1
2
3
4
5
6
public long fibonacci(int n) {
  if (n < 2) return 1;
  double goldenRatio = (1 + Math.sqrt(5)) / 2;
  double otherRatio = (1 - Math.sqrt(5)) / 2;
  return Math.round((Math.pow(goldenRatio, n) - Math.pow(otherRatio, n)) / Math.sqrt(5));
}

类似的问题会有简单的变种，比如爬楼梯问题

爬楼梯问题

Climbing Stairs
这里的递推公式其实是一致的，$$f(n) = f(n - 1) + f(n - 2)$$
只是最开始的前3项数列值不同罢了，a[0] = 0, a[1] = 1, a[2] = 2, a[3] = 3 ……

1
2
3
4
5
6
public long climbStairs(int n) {
  if (n <= 0) return 0;
  double goldenRatio = (1 + Math.sqrt(5)) / 2;
  double otherRatio = (1 - Math.sqrt(5)) / 2;
  return Math.round((Math.pow(goldenRatio, n + 1) - Math.pow(otherRatio, n + 1)) / Math.sqrt(5));
}

换硬币

Coin Change
如果将目标数额换成台阶数，给定的硬币面额换成可以走的步数，那么这个问题就转化成了爬楼梯的问题。

这里我们简单验证下DP问题的特征，无后效性（当前选择的硬币方案不会对之前的选择有影响）、重复子问题（数额从 1 到 i的问题求解是同样的子问题），和最优子结构（一旦数额确定，那么换硬币最少个数也是确定的）。所以符合DP求解问题的特征。下面我们用DP来求解该问题：

状态定义： $dp[i]: 数额为i的最小硬币个数$
状态转移方程： $dp[i] = Min(dp[i - coins[j]]) + 1$
结果所在：$dp[amount]$
时间复杂度 $O(amount * coins.length)$

对应代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int coinChange(int[] coins, int amount) {
  if (coins == null || coins.length == 0 || amount < 0) {
    return -2;
  }

  int[] dp = new int[amount + 1];
  for (int i = 0; i < amount + 1; i++) {
    dp[i] = amount + 1;
  }
  dp[0] = 0;
  for (int i = 1; i <= amount; i++) {
    //
    for (int coin : coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

三角形最小路径和

原题传送门

无后效性，和重复子问题是显而易见的， 对于数组的某一个点(i,j)到着一点的最小路径和也是确定的，所以最优子结构也是成立的，符合DP解决问题的特征。下面用DP来求解：

状态定义: $dp[i][j] : 从最下一层三角形到 i,j 点的最小路径和$。

状态转移方程: $dp [i][j] = Min (dp[i + 1][j] , dp[i + 1][j + 1]) + array[i][j];$

时间复杂度: $O(m \cdot n)$ 其中$m$,$n$代表三角形的高度和底长度

对应代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minimumTotal(List<List<Integer>> triangle) {
  int lineSize = triangle.size();
  int colMaxSize = triangle.get(lineSize - 1).size();

  int [][] dp = new int[lineSize][colMaxSize];
  for (int k = 0; k < colMaxSize; k++) {
    dp[lineSize - 1] [k] = triangle.get(lineSize - 1).get(k);
  }

  for (int i = lineSize - 2; i >= 0; i--) {
    int columnSize = triangle.get(i).size();
    for (int j = 0; j <= columnSize - 1; j++) {
      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
    }
  }

  return dp[0][0];
}

乘积最大子序列

原题传送门

同样，无后效性、重复子问题是显然的，对于数组的第i个位置之前的子数组乘积最大子序列也是确定的，所以最优子结构也成立，符合DP解决问题特征。

状态定义： $dpPos[i]: 从数组下标0位置到i位置的乘积最大子序列值，dpNeg[i]从数组下标0位置到i位置的乘积负数最大子序列值$
状态转移方程:

$$
dpPos[i] = Max(dpPos[i - 1] \times nums[i], dpNeg[i - 1] \times nums[i], nums[i]) \
dpNeg[i] = Min(dpPos[i - 1] \times nums[i], dpNeg[i - 1] \times nums[i], nums[i])
$$

时间复杂度: $O(n)$
对应代码实现： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxProduct(int[] nums) {
  if (nums == null || nums.length == 0) return -1;

  int[] dpPositive = new int[nums.length];
  int[] dpNegative = new int[nums.length];
  dpNegative[0] = nums[0];
  dpPositive[0] = nums[0];
  int result = nums[0];

  for (int i = 1; i < nums.length; i++) {
    dpPositive[i] =
        Math.max(Math.max(dpPositive[i - 1] * nums[i], dpNegative[i - 1] * nums[i]), nums[i]);
    dpNegative[i] =
        Math.min(Math.min(dpPositive[i - 1] * nums[i], dpNegative[i - 1] * nums[i]), nums[i]);
    result = Math.max(result, dpPositive[i]);
  }

  return result;
}

最长递增子序列问题（Longest Increasing Subsequence）

原题传送门

拿到题目首先审题，能想到的问题会是什么？空数组怎么办？数组内的元素会不会有相邻相等的情况？当然这些都是你需要和面试官沟通的内容。

无后效性、重复子问题是显而易见的，对于数组i位置之前的子数组的最大递增子序列也是确定的，所以最优子结构也成立，符合DP解决问题的特征。

状态定义：$dp[i] 从头到第i个元素（选中第i个元素）最长子序列的长度$
状态转移方程：
$$
dp[i] = Max{dp[j]} + 1 (j: 0-> i -1 a[i] < a[j])
$$
所求解的值：
$$
Max(dp[0], dp[1], dp[2] …dp[n])
$$

时间复杂度： $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int lengthOfLIS(int[] nums) {
  if (nums == null || nums.length == 0) {
    return 0;
  }

  int result = 1;
  int[] dp = new int[nums.length];
  int length = nums.length;
  for (int i = 0; i < nums.length; i++) {
    dp[i] = 1;
  }
  for (int i = 0; i < length; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    result = Math.max(result, dp[i]);
  }

  return result;
}

本题还有一个follow up， 要求寻找时间复杂度为$O(nlog^n)$的算法， 这个算法虽然存在，但跳出了DP的解题范围， 所以暂时就留一个TODO 作为题目完整性的补充（之后再来填坑）

1
2
3
4
// TODO: Algorithm with time complexity O(nlog^n)
 public int lengthOfLIS(int[] nums) {
 }

编辑距离（Edit Distance/Levinstein Distance）

Edit Distance
这里解决编辑距离问题有几种常见思路，比如以一个字符串为目标字符串，对另一个字符串采取BFS/DFS“编辑操作”，然后记录编辑深度，在字符相等的时候停止，在所有可能的编辑方案中找出最小编辑距离。
由于这里是动态规划的专题，所以下面的方案主要围绕如何使用DP来解决该问题

首先是状态定义$minED(i, j)$表示word1的第i位之前的子字符串与word2的第j位之前子字符串的最小编辑距离
其中 $i = 0, 1 … len(word1); j = 0, 1…len(word2)$

状态转移方程：

$$
minED(i,j) =
\begin{cases}
minED(i - 1, j - 1), & \text{word1[i - 1] = word2[j - 1]}\
1 + min(minED(i - 1, j), minED(i - 1, j - 1), minED(i - 1, j + 1)), & \text{word1[i - 1] != word2[j - 1]}
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int minDistance(String word1, String word2) {
  if (word1 == null && word2 == null) {
    return 0;
  } else if (word1 == null && word1 != null) {
    return word2.length();
  }

  int[][] minEditDistance = new int[word1.length() + 1][word2.length() + 1];

  // minEditDistance (i, j) :
  // word1 pre i char edit change to word2 pre j sub-string minEditDistance

  for (int i = 0; i < word1.length() + 1; i++) {
    minEditDistance[i][0] = i;
  }

  for (int j = 0; j < word2.length() + 1; j++) {
    minEditDistance[0][j] = j;
  }

  for (int i = 1; i < word1.length() + 1; i++) {
    for (int j = 1; j < word2.length() + 1; j++) {

      if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        minEditDistance[i][j] = minEditDistance[i - 1][j - 1];
      } else {
        minEditDistance[i][j] = Math.min(minEditDistance[i - 1][j],
            Math.min(minEditDistance[i][j - 1], minEditDistance[i - 1][j - 1])) + 1;
      }
    }
  }

  return minEditDistance[word1.length()][word2.length()];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minDistance(self, word1, word2):
    """
    :type word1: str
    :type word2: str
    :rtype: int
    """
    _min_distance = [[0 for j in xrange(len(word2) + 1)] for i in xrange(len(word1) + 1)]

    for i in xrange(len(word1) + 1):
        _min_distance[i][0] = i

    for j in xrange(len(word2) + 1):
        _min_distance[0][j] = j

    for i in xrange(1, len(word1) + 1):
        for j in xrange(1, len(word2) + 1):
            if word1[i - 1] == word2[j - 1]:
                _min_distance[i][j] = _min_distance[i - 1][j - 1]
            else:
                _min_distance[i][j] = 1 + min(_min_distance[i - 1][j], _min_distance[i][j - 1],
                                              _min_distance[i - 1][j - 1])

    return _min_distance[len(word1)][len(word2)]

买股票系列问题

最简单的买股票时机问题

Best Time to Buy and Sell Stock
只允许交易一次（买入一次、卖出一次）的限制。

首先关于题目目前没有太多需要沟通的点，对于传入的参数做好必要的防御性编程就好。

首先看下所有可行解：

  • 直觉算法（暴力法）

解法1查找数组的最小值， 然后从这个最小值位置开始到数组结束为止找出这个子数组的最大值，然后将最大值减去最小值，两者的差值就是所求最大利润值。
时间复杂度： 两次遍历数组$O(n)$
空间复杂度： $O(1)$

  • DP

首先无后项性和重复子问题的特性是显而易见的， 对于最优子结构，第i天的最大利润值其实也是确定的，所以最优子结构也是成立的。 下面我们尝试使用动态规划的思路来解决这个问题。

状态定义： $mp(i) 表示第i天最大利润$
状态转移方程：
$$
mp(i) =
\begin{cases}
mp(i - 1) - a[i], & \text{买股票} \
mp(i - 1) + a[i], & \text{卖股票}
\end{cases}
$$
到这里我们发现对于买卖股票的操作无法用现有的状态定义了，说明现有的状态定义可能是缺少了维度，因此我们DP的定义进入了第二个版本：

状态定义2.0
状态定义： $mp(i, j) j = 0,1; mp(i, 0) 表示第i天未持有股票，mp(i, 1) 表示第i天持有股票$
似乎这里的定义还是有问题的，就是忽略了只能交易一次的限制，添加一个是否交易过（或者交易次数）的维度是否就可以呢？

当然下面的题目中还有一个泛化的k次交易限制的问题，可以使用k次的问题（k=1）来求解该题。

同一股票可以交易无数次（买之前需要将之前买进的股票卖出）

Best Time to Buy and Sell Stock II

我们发现对上面的状态做简单的修改就可以适用本题
状态定义： $mp(i,j) j = 0,1; mp(i,0) 表示第i天未持有，mp(i,1) 表示第i天持有股票$
状态转移方程：
$$
mp(i,0) = Max
\begin{cases}
mp(i - 1,0), & \text{i-1天持有}\
mp(i - 1,1) + a[i], & \text{i-1天未持有，第i天买入}
\end{cases}
$$

$$
mp(i,1) = Max
\begin{cases}
mp(i - 1, 1), & \text{i-1天未持有}\
mp(i - 1, 0) - a[i], & \text{i-1天持有， 第i天卖出}
\end{cases}
$$

同时如果细心你会发现，这其实也是交易K次泛化问题的一种特殊条件(k=N//2)。

交易两次，不能同时拥有两只股票

Best Time to Buy and Sell Stock III

交易两次其实是下面泛化K次的特殊情况（k=2），所以可以考虑先解决下面的k次泛化问题。

交易K笔，不能同时拥有两只股票

Best Time to Buy and Sell Stock IV

状态定义： $mp(i, j, k) 表示第i天最大利润 – j: 0 未持有股票 1 持有股票 – k：之前交易次数$
状态转移方程：
$$
mp(i, 0, k) = Max
\begin{cases}
mp(i-1, 0, k), & \text{}\
mp(i-i, 1, k-1) + a[i], & \text{}
\end{cases}
$$

$$
mp(i, 1, k) = Max
\begin{cases}
m([i-1, 1, k), & \text{}\
mp(i-1, 0, k-1) - a[i], & \text{}
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int maxProfitklimitedTransaction(int k, int[] prices) {

  if (prices == null || prices.length == 0) {
    return 0;
  }

  int[][][] maxProfit = new int[prices.length][2][k + 1];
  for (int l = 0; l < k + 1; l++) {
    maxProfit[0][0][l] = 0;
    maxProfit[0][1][l] = -prices[0];
  }

  for (int i = 1; i < prices.length; i++) {
    for (int l = 1; l < k + 1; l++) {
      maxProfit[i][0][l] = Math.max(maxProfit[i - 1][0][l], maxProfit[i - 1][1][l] + prices[i]);
      maxProfit[i][1][l] = Math
          .max(maxProfit[i - 1][1][l], maxProfit[i - 1][0][l - 1] - prices[i]);
    }
  }

  int maxProfitResult = 0;
  for (int l = 0; l < k + 1; l++) {
    maxProfitResult = Math.max(maxProfitResult, maxProfit[prices.length - 1][0][l]);
  }

  return maxProfitResult;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def max_profit_klimited_transaction(self, k, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if not prices:
        return 0

    _MAX_TRANSACTION_NUM = k

    _max_profit = [[[0 for l in xrange(_MAX_TRANSACTION_NUM + 1)] for j in xrange(2)] for i in xrange(len(prices))]

    for l in xrange(_MAX_TRANSACTION_NUM + 1):
        _max_profit[0][0][l] = 0
        _max_profit[0][1][l] = - prices[0]

    for i in xrange(1, len(prices)):
        for l in xrange(_MAX_TRANSACTION_NUM):
            _max_profit[i][0][l] = max(_max_profit[i - 1][1][l] + prices[i], _max_profit[i - 1][0][l])
            _max_profit[i][1][l] = max(_max_profit[i - 1][0][l - 1] - prices[i], _max_profit[i - 1][1][l])

    return max(_max_profit[len(prices) - 1][0])

到这里会发现，其实限制条件越多，用DP去解决问题所需要的维度就越多。

交易有冻结期

Best Time to Buy and Sell Stock with Cooldown

拥有冻结期其实就是在没有交易次数限制的题目上扩展了一个状态“cooldown”，从而在状态定义和状态转移方程的时候需要做对应的调整：

状态定义：$mp(i, j) j = 0,1,2 ; mp(i, 0) 表示第i天未持有，mp(i, 1) 表示第i天持有股票, mp(i, 2)处于交易冻结状态$

由于卖出股票后（即未持有股票状态）会转变为交易冻结状态，之后冻结状态会转变为未持有状态或者持有状态（这里建议画一个状态转移图，写状态转移方程的时候会更清晰些）。

状态转移方程：

$$
mp(i, 0) = Max
\begin{cases}
mp(i - 1, 0), & \text{i-1天持有}\
mp(i - 1, 1) + a[i], & \text{i-1天未持有，第i天买入}\
mp(i - 1, 2), &\text{i-1天处于冻结期，第i天未操作}
\end{cases}
$$

$$
mp(i, 1) = Max
\begin{cases}
mp(i - 1, 1), & \text{i-1天未持有}\
mp(i - 1, 2) - a[i], & \text{i-1天处于， 第i天买入}
\end{cases}
$$

$$
mp(i, 2) = mp(i - 1, 0)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int maxProfitWithCooldown(int[] prices) {
  if (prices == null || prices.length == 0) {
    return 0;
  }

  int[][] maxProfit = new int[prices.length][3];
  // maxProfit(i, j, k)
  //  i: 0, 1, ... prices.length
  //  j: 0, 1
  //  i means i-th day
  //  j means stock holding status, 0 Not holding, 1 holding, 2 Cool down
  for (int j = 0; j < 3; j++) {
    maxProfit[0][0] = 0;
    maxProfit[0][1] = -prices[0];
    maxProfit[0][2] = 0;
  }

  for (int i = 1; i < prices.length; i++) {
    maxProfit[i][0] = Math.max(maxProfit[i - 1][1] + prices[i], Math.max(maxProfit[i - 1][0], maxProfit[i - 1][2]));
    maxProfit[i][1] = Math.max(maxProfit[i - 1][1], maxProfit[i - 1][2] - prices[i]);
    maxProfit[i][2] = maxProfit[i - 1][0];
  }

  int maxProfitResult = 0;
  for (int k = 0; k < 3; k++) {
    maxProfitResult = Math.max(maxProfitResult, maxProfit[prices.length - 1][k]);
  }

  return maxProfitResult;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxProfitWithCooldown(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if not prices:
        return 0

    _max_profit = [[0 for j in xrange(3)] for i in xrange(len(prices))]

    _max_profit[0][0] = 0
    _max_profit[0][1] = -prices[0]
    _max_profit[0][2] = 0

    for i in xrange(1, len(prices)):
        _max_profit[i][0] = max(_max_profit[i - 1][0], _max_profit[i - 1][1] + prices[i], _max_profit[i - 1][2])
        _max_profit[i][1] = max(_max_profit[i - 1][1], _max_profit[i - 1][2] - prices[i])
        _max_profit[i][2] = _max_profit[i - 1][0]

    return max(_max_profit[len(prices) - 1])

交易有手续费

Best Time to Buy and Sell Stock with Transaction Fee

这里的交易有手续费实际上是基于在没有交易次数限制的题目上扩展了一个交易费用扣除的条件，只需要在买入或卖出时扣除即可（注意：不要在买入和卖出都扣除）

状态定义： $mp(i,j) j = 0,1; mp(i,0) 表示第i天未持有，mp(i,1) 表示第i天持有股票$
状态转移方程：
$$
mp(i,0) = Max
\begin{cases}
mp(i - 1,0), & \text{i-1天持有}\
mp(i - 1,1) + a[i] - fee, & \text{i-1天未持有，第i天买入}
\end{cases}
$$

$$
mp(i,1) = Max
\begin{cases}
mp(i - 1, 1), & \text{i-1天未持有}\
mp(i - 1, 0) - a[i], & \text{i-1天持有， 第i天卖出}
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxProfitWithTransactionFee(int[] prices, int fee) {
  if (prices == null || prices.length == 0 || fee < 0) {
    return 0;
  }

  int[][] maxProfit = new int[prices.length][2];

  maxProfit[0][0] = 0;
  maxProfit[0][1] = -prices[0];

  for (int i = 1; i < prices.length; i++) {
    maxProfit[i][0] = Math.max(maxProfit[i - 1][0], maxProfit[i - 1][1] + prices[i] - fee);
    maxProfit[i][1] = Math.max(maxProfit[i - 1][1], maxProfit[i - 1][0] - prices[i]);
  }

  return maxProfit[prices.length - 1][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxProfitWithTransactionFee(self, prices, fee):
    """
    :type prices: List[int]
    :type fee: int
    :rtype: int
    """
    if not prices or fee < 0:
        return 0

    _max_profit = [[0 for j in xrange(2)] for i in xrange(len(prices))]
    _max_profit[0][0] = 0
    _max_profit[0][1] = -prices[0]

    for i in xrange(1, len(prices)):
        _max_profit[i][0] = max(_max_profit[i - 1][0], _max_profit[i - 1][1] + prices[i] - fee)
        _max_profit[i][1] = max(_max_profit[i - 1][1], _max_profit[i - 1][0] - prices[i])
    return _max_profit[len(prices) - 1][0]
文章目录
  1. 1. 什么样的问题适合用DP来解决
  2. 2. 使用DP来解决问题的特征
  3. 3. DP问题思考和解决的过程是怎样的
  4. 4. DP问题的程序模版是怎样的
  5. 5. 一些适合DP的经典问题
    1. 5.1. Fibonacci 数列
  6. 6. 爬楼梯问题
  7. 7. 换硬币
  8. 8. 三角形最小路径和
  9. 9. 乘积最大子序列
  10. 10. 最长递增子序列问题（Longest Increasing Subsequence）
  11. 11. 编辑距离（Edit Distance/Levinstein Distance）
  12. 12. 买股票系列问题
    1. 12.1. 最简单的买股票时机问题
    2. 12.2. 同一股票可以交易无数次（买之前需要将之前买进的股票卖出）
    3. 12.3. 交易两次，不能同时拥有两只股票
    4. 12.4. 交易K笔，不能同时拥有两只股票
    5. 12.5. 交易有冻结期
    6. 12.6. 交易有手续费