小白学DP(动态规划)_构建dp数组什么情况下是【0】x n ,什么情况下是【0】x n+1

动态规划

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

概念

动态规划（英语： Dynamic programming，简称 DP） 是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划算法的核心就是记住已经解决过的子问题的解；而记住求解的方式有两种：

自顶向下的备忘录法

比如：斐波拉契数列 Fibonacci。

public static int fibonacci(int n) {
	if (n <= 1)
		return 1;
	if (n == 2)
		return 2;
	return fibonacci(n-1) + fibonacci(n-2);
}
1
2
3
4
5
6
7

我们分析以前写过的递归就会发现有很多节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。

public class Fibonacci {
	public static void main(String[] args) {
		//创建备忘录
		int[] memo = new int[n+1];
		System.out.println(fibonacci(7));
	}
	/**
	 * 自顶向下备忘录法
	 * @param n
	 * @param memo	备忘录
	 * @return
	 */
	public static int fibonacci(int n, int[] memo) {
		// 如果已经求出了fibonacci（n）的值直接返回
		if(memo[n] != 0) return memo[n];
		// 否则将求出的值保存在 memo 备忘录中。
		if(n<=2)
			memo[n]=1;
		else {
			memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
		}
		return memo[n];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这个方法是由上至下，比如求f(5),我们要求f(4)和f(3)，求出来后放入备忘录，当求f(4)时需要f(3)和f(2)，我们可以直接从备忘录取f(3)而不是再去求一遍。

自底向上的动态规划

备忘录法是利用了递归，上面算法不管怎样，计算 fib（6）的时候最后还是要计算出 fib（1）， fib（2）， fib（3） ……,那么何不先计算出 fib（1）， fib（2）， fib（3） ……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

public class FibonacciPlus {
	/**
	 * 自底向上的动态规划
	 * @param n
	 * @return
	 */
	public static int fib(int n) {
		if(n<=0)return -1;
		//创建备忘录
		int[] memo = new int[n+1];
		memo[0]=0;
		memo[1]=1;
		for(int i=2;i<=n;i++) {
			memo[i]=memo[i-1]+memo[i-2];
		}
		return memo[n];
	}
	/**
	 * 参与循环的只有 i， i-1 , i-2 三项，可以优化空间
	 * @param n
	 * @return
	 */
	public static int fibPlus(int n) {
		if(n<=0)return -1;
		int memo_i_2=0;
		int memo_i_1=1;
		int memo_i=1;
		for(int i=2;i<=n;i++) {
			memo_i = memo_i_1+memo_i_2;
			memo_i_2 = memo_i_1;
			memo_i_1 = memo_i;
		}
		return memo_i;
	}
}
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
35

例题

区域和检索－数组不可变

问题描述：

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

解法：
－ 暴力循环从下标i到j求和，如果检索次数较多，则会超出时间限制。
－ 降低时间复杂度，最理想情况O（1），求前缀和，sumRange(i, j) = （0－j+1）－（0－i-1的和）

代码：
Java版

class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Python版

class NumArray:

    def __init__(self, nums: List[int]):
        self.sums = [0]
        _sums = self.sums

        for num in nums:
            _sums.append(_sums[-1] + num)

    def sumRange(self, i: int, j: int) -> int:
        _sums = self.sums
        return _sums[j+1] - _sums[i]
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析：

－ 时间复杂度：
初始化需要O(n)，每次检索、O(1)，其中n是nums的长度。
初始化需要检索遍历数组nums的前缀和，时间复杂度O(n)。

－ 空间复杂度:
空间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。需要创建一个长度为 n+1n+1 的前缀和数组

使用最小花费爬楼梯

问题描述：

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

解法：

假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n-1，楼层顶部对应下标 n，问题等价于计算达到下标 nn 的最小花费。可以通过动态规划求解。
创建长度为n＋1的数组dp，dp[i]代表达到下标i的最小花费。
由于可以选择下标 00 或 11 作为初始阶梯，因此dp[0]=dp[1]=0。
当 2≤i≤n 时，可以从下标 i-1 使用 cost[i-1]的花费达到下标 i，或者从下标 i−2 使用cost[i-2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

Java版：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11

Python版：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0, 0]
        n = len(cost)
        for i in range(2, n+1):
            dp.append(min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]))
        return dp[n]
1
2
3
4
5
6
7

优化版：
上述代码的时间复杂度和空间复杂度都是 O(n)。注意到当 i≥2 时，dp[i] 只和 dp[i−1] 与 dp[i−2] 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int pre = 0, cur = 0, next = 0;
        for (int i = 2; i <= n; i++) {
            next = Math.min(cur+cost[i-1], pre + cost[i-2]);
            pre = cur;
            cur = next;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 cost 的长度。需要依次计算每个 dp 值，每个值的计算需要常数时间，因此总时间复杂度是 O(n)。

空间复杂度：O(1)。使用滚动数组的思想，只需要使用有限的额外空间。

小白上楼梯（三步问题）

爬楼梯一次可以爬一步，两步，三步，问爬到n阶台阶的方法

Java版 递归：

static int f(int n) {
	if (n == 0) return 1;
	if (n == 1) return 1;
	if (n == 2) return 2;
	return f(n-1)+f(n-2)+f(n-3);
}
1
2
3
4
5
6

Python版 递推：

class Solution:
    def waysToStep(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 4
        a = 1; b = 2; c = 4; d = 0
        for i in range(4, n+1):
            d = ((a+b) % 1000000007 + c) % 1000000007
            a = b
            b = c
            c = d
        return d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

小白上楼梯2

爬楼梯每次至少爬d阶，爬到n阶台阶的方案数
动态规划，每次向前推d，第i-d的阶数方案会对下一次造成影响。

int sum = 1;
int mod = 1000000007;
System.out.println(mod);
for (int i = d; i <= n; i++) {
    sum += x[i-d];
    x[i] += sum;
    x[i] %= mod;
    sum %= mod;
}
System.out.println(x[n]);
1
2
3
4
5
6
7
8
9
10

最大字段和

给定序列，找出最大的子段和
累加每个元素，当sum<0,将其初始化为0（前缀和的思想）

每次都有前面最长连续和＋上当前与不加当前值的两种选择

long sum = 0, max = 0;
for (int i = 0; i < n; i++) {
     sum += x[i];
     max = Math.max(max, sum);
     if (sum < 0)
         sum = 0;
 }
 System.out.println(max);
1
2
3
4
5
6
7
8

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
           nums[i] += max(nums[i-1], 0)
        return max(nums)
1
2
3
4
5

最长公共子串

在字符串中任意个连续的字符组成的子序列成为该串的子串，给定两个字符串，求出最长的公共子串的长度
思想：从头遍历一个字符串，当字符串不包含则将指针++

String s = sc.nextLine();
String x = sc.nextLine();
 int max = 0, i = 0;
 StringBuilder sb = new StringBuilder();
 for (char c : s.toCharArray()) {
     sb.append(c);
     String ss = sb.substring(i);
     if (x.contains(ss)) {
         max = Math.max(max, ss.length());
     } else {
         i++;
     }
 }
 System.out.println(max);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最长公共子序列

• 最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。什么是子序列呢？ 即一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢 给定串中任意个连续的字符组成的子序列称为该串的子串。

• 举个例子（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），

  • 假如S1的最后一个元素与S2的最后一个元素相等，那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。
  • 假如S1的最后一个元素与S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的LCS就等于： {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

int[] x = {0, 2, 5, 7, 3, 6, 8, 4};
int[] y = {0, 3, 4, 7, 3, 6, 4};
int[][] xx = new int[x.length+1][y.length+1];
for (int i = 1; i < x.length; i++) {
    for (int j = 1; j < y.length; j++) {
        if (x[i] == y[j])
            xx[i][j] = xx[i-1][j-1]+1;
        else
            xx[i][j] = Math.max(xx[i-1][j], xx[i][j-1]);
    }
}
System.out.println(xx[x.length-1][y.length-1]);
1
2
3
4
5
6
7
8
9
10
11
12

• 输出最长公共子序列
  类似的倒推回去：当x[n] i= y[n]时，比较xx[i-1][j]与x[i][j-1]如果若大于就选i-1与j反之选择i与j-1，当等于时选择不同的方向有不同的结果。

int i = x.length-1, j = y.length-1;
StringBuilder sb = new StringBuilder();
while (xx[i][j] > 0) {
    if (x[i] == y[j]) {
        sb.append(x[i]);
        i--;
        j--;
    } else if (x[i] != y[j]) {
        if (xx[i - 1][j] > xx[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
}
System.out.println(sb.reverse().toString());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最长递增子序列

• DP-动态规划
  状态设计：用一个维护数组dp[i]表示以a[i]结尾的最长递增子序列的长度
  状态转移：之后向前找到一个小于a[i]的进行状态转移dp[i] = Math.max(dp[i], dp[j]+1);
  边界处理：dp[i]=1（0<=j<n）
  时间复杂度：O(n2)

int[] x = {3, 1, 2, 1, 8, 5};
// dp[i]表示以a[i]结尾的最长递增子序列的长度
dp = new int[x.length];
int ans = 0;
for (int i = 0; i < x.length; i++) {
    // 初始化每一个dp[i]=1
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
        if (x[i] > x[j])
            dp[i] = Math.max(dp[i], dp[j]+1);  // 状态转移
    }
    ans = Math.max(ans, dp[i]);  // 比较每一个dp，取最大值
}
System.out.println(ans);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 贪心+二分查找
  利用贪心的思想，对于一个上升的子序列，显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。
  因此，我们只需要维护dp数组，其表示就是长度为i+1的LIS结尾元素的最小值，保证每一位都是最小值
  dp数组单调递增，因此对于每一个a[i]，先判断是否可以直接插入到dp数组尾部，即比较其与dp数组的最大值，即最后一位；如果不可以则找出dp数组中第一个大于等于a[i]的位置，用a[i]替换之。

int[] dp2 = new int[x.length];
int index = 0;
dp2[0] = x[0];
for (int i = 1; i < x.length; i++) {
    if (x[i] > dp2[index])
        dp2[++index] = x[i];
    else
        dp2[bin(index, x[i])] = x[i];
}
System.out.println(index+1);

// 二分查找
public static int bin(int e, int x) {
int s = 0;
while (s < e) {
    int mid = (s + e) >>> 1;
    if (dp[mid] < x)
        s = mid+1;
    else
        e = mid-1;
}
return s;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

按摩师

• 问题描述
  一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

• 解析：
  每一次都与前面的选择有关，递推试为：当前不选择，则前面的就是当前的最大值或者选择就是前一个的前一个

• 代码：

class Solution {
    public int massage(int[] nums) {
        if (nums.length == 0)
            return 0;
            
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > 1)
                dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
            else
                dp[i] = Math.max(dp[i-1], nums[i]);
        }
        return dp[nums.length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

只有两个键的键盘

最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) :你可以粘贴你上一次复制的字符。 给定一个数字 n 。
你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。

算法：
假设 g_1, g_2, … 就是 N 的素数分解，则需要的最少操作等于这些素数之和。

复杂度分析

时间复杂度：O( sqrtN )，当 N 是素数的平方时，需要循环 O(sqrtN) 步。

空间复杂度：O(1)，ans 和 d 的存储空间。

代码：

class Solution(object):
    def minSteps(self, n):
        ans = 0
        d = 2  # 2 是最小的素数因子，所以从 2 开始
        while n > 1:
            while n % d == 0:  # 如果 d 仍然是当前 n 的最小素数因子，继续遍历
                ans += d
                n /= d
         	# 如果此时 d 不是当前 n 的最小素数因子了，那么 d++ 继续试探
    		# 其实此处应该是把 d 变为比 d 大的下一个素数，但是我们没有必要在构建出一个素数因子的数组
    		# 因为得不偿失(还需要创建一个判断是否为素数的方法)，那会花费更多的时间和空间，不如让计算机一个个去试就好了
            d += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

等差数列

函数要返回数组 A 中所有为等差数组的子数组个数。

解法：

• 暴力
  对于每一个差值都向后遍历，若相等，则++，否则break;

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        cnt = 0
        for i in range(len(nums)-2):
            d = nums[i+1]-nums[i]
            for j in range(i+2, len(nums)):
                if (nums[j] - nums[j-1] == d):
                    cnt += 1
                else:
                    break
        return cnt
1
2
3
4
5
6
7
8
9
10
11

• 递归
  自顶向下：从后向前，如果如果第 i 个元素与前一个元素的差值正好等于之前的差值，我们直接就可以算出新增的等差数组的个数 ap，同时可以更新 sum。但是，如果新元素跟前一个元素的差值不等于之前的差值，也就不会增加等差数列的个数。
  代码：

class Solution {
    int sum = 0;
    public int numberOfArithmeticSlices(int[] A) {
        slices(A, A.length-1);
        return sum;
    }
    public int slices(int[] A, int i) {
        if (i < 2)
            return 0;
        int ap = 0;
        if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
            ap = 1 + slices(A, i-1);
            sum += ap;
        } else {
            slices(A, i-1);
        }
        return ap;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• DP
  与递归方法相反，我们从前向后推导，其余思路类似，对于第i个数，判断该元素跟前一个元素的差值是否相同。如果相等则当前新区间中等差数列的个数即为1+dp[i-1]。sum+上这个值更新
  dp[i] 以A[i]结尾的等差数列个数

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int[] dp = new int[nums.length];
         int sum = 0;
         for (int i = 2; i < dp.length; i++) {
             if (nums[i]-nums[i-1] == nums[i-1]-nums[i-2]) {
                 dp[i] = dp[i-1] + 1;
                 sum += dp[i];
             }
         }
         return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 常数空间的动态规划

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        cnt = 0
        dp = 0
        for i in range(2, len(nums)):
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]):
                dp = dp+1;
                cnt += dp;
            else:
                dp = 0
        return cnt
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

时间复杂度：O（n）
只需遍历数组A一次，其大小为n

空间复杂度：O(1)
只需常数个额外空间

无矛盾的最佳球队

题目描述

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于
一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

分析:
根据题目描述，组建球队首先队员之间不能有矛盾，即：年龄小的得分不能大于年龄高的得分。

因此需要找得分最高的组合，即寻找最大上升子序列。

我们可以按照年龄升序，年龄相同则分数升序，即可 转化为最大上升子序列

即当分数大于/等于当前队伍最后一个队员的分数时就加入队伍，并更新max，不需考虑年龄。

解法：

在Python中

• 内置函数zip很方便将两个数组对应位置元素压缩为一个元组，这些元组组成列表。
• 内置函数sort默认升序排序，我们可以自定义排序关键字key使用匿名表达式lambda
  arr.sort(key = lambda x: (x[0], x[1]))
  如该例子就是以x[0]排序，备用是x[1]排序
• 最后返回dp中最大值，max(dp)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        arr = list(zip(ages, scores))
        arr.sort(key = lambda x: (x[0], x[1]))

        dp = [arr[i][1] for i in range(n)]
        for i in range(n):
            for j in range(i):
                if (arr[i][1] >= arr[j][1]):
                    dp[i] = max(dp[i], dp[j]+arr[i][1])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12

Java版：
对于如何将两个数组合为一起，我起初想创建一个class，发现麻烦了，大多时候创建二维数组还是挺多的，一行对应一个对象。两列分别代表属性，比如：年龄，分数

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        if (scores.length == 1)
            return scores[0];
        int[][] arr = new int[scores.length][2];
        // 将两个内容合并为一行,一行代表一个队员
        for (int i = 0; i < scores.length; i++) {
            arr[i][0] = ages[i];
            arr[i][1] = scores[i];
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];  // 分数升序
                return o1[0] - o2[0];
            }
        });
        int[] dp = new int[scores.length];
        // 初始化dp[i]代表第i个球员为队伍末尾时，队伍最大分数
        for (int i = 0; i < scores.length; i++) {
            dp[i] = arr[i][1];
        }
        int max = 0;
        for (int i = 0; i < scores.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i][1] >= arr[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i][1]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
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

最佳买卖股票时机(冷冻期)

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，
• 你无法在第二天买入股票 (即冷冻期为 1 天)。

方法一：动态规划

思路与算法

我们用 f[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：

• 我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；

• 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；

• 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]。

这里的「处于冷冻期」指的是在第 ii 天结束之后的状态。也就是说：如果第 ii 天结束之后处于冷冻期，那么第 i+1i+1 天无法买入股票。

推导式：

• f[i][0]：代表第i天持有股票的最大收益，那么该股票可能来自第i-1天的股票未卖，或者是第i天买的，那么第i-1天必须是f[i-1][2]，未持有股票且不在冷冻期+上当天买入的股票负收益。
• f[i][1]：代表第i天处于冷冻期，则一定是第i-1天卖了股票
• f[i][2]：代表不持股票，不出与冷冻期，则可能是i-1天处于冷冻期，或者是i-1天不处于冷冻期。

结果是： Math.max(f[n-1][1], f[n-1][2]);
f[n-1][0]:持有股票是无意义的。

代码：

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int n = prices.length;
        // f[i][0]：手上持有股票的最大收益
        // f[i][1]：手上不持有股票，且处于冷冻期的累计最大收益
        // f[i][2]：手上不持有股票，且不在冷冻期的累计最大收益
        int[][] f = new int[n][3];
        f[0][0] = -prices[0];  // 即第一天买入
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i-1][0], f[i-1][2]-prices[i]);
            f[i][1] = f[i-1][0] + prices[i];
            f[i][2] = Math.max(f[i-1][1], f[i-1][2]);
        }
        return Math.max(f[n-1][1], f[n-1][2]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

空间优化:
我们注意到当天至于前一天有关，因此使用三个变量将前天数据存储就行，通过他们计算当天的。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        f0, f1, f2 = -prices[0], 0 ,0

        for i in range(1, n):
            new0 = max(f0, f2-prices[i])
            new1 = f0 + prices[i]
            new2 = max(f1, f2)
            f0, f1, f2 = new0, new1, new2

        return max(f1, f2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

参考Leetcode题解
感谢！

最佳买卖股票时机(手续费)

跟前面的类似，当天有股票与没有股票，只用加上手续费即可

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        f0, f1 = 0, -prices[0]

        for i in range(1, n):
            new0 = max(f0, f1 + prices[i] - fee)  # 没有股票
            new1 = max(f1, f0 - prices[i])  # 有股票
            
            f0, f1 = new0, new1

        return 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

香槟塔

我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

思路
我们可以直接模拟整个过程。我们记录流入每个杯子的香槟的数量之和，例如对于一个杯子，流入的香槟数量为 10。由于这个数值大于 1，因此会有 9 数量的香槟流出这个杯子，并且会有 4.5 数量的香槟分别流入这个杯子下面的两个杯子中。以此类推。

总的来说，如果流入一个杯子的香槟数量为 X，且 X 大于 1，那么就会有 Q = (X - 1.0) / 2 数量的香槟流入下面的两个杯子中。我们可以从第一层的杯子开始，计算出第二层每个杯子中流入的香槟数量，再计算出第三层的数量，直到计算到第 query_row 层。

代码：

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] A = new double[102][102];
        A[0][0] = (double)poured;
        for (int r = 0; r <= query_row; r++) {
            for (int c = 0; c <= r; c++) {
                double q = (A[r][c] - 1.0) / 2.0;
                if (q > 0) {
                    A[r+1][c] += q;
                    A[r+1][c+1] += q;
                }
            }
        }
        return Math.min(1, A[query_row][query_glass]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16