动态规划（Dynamic Programming）

动态规划问题参考算法导论第15章，动态规划的核心思想在于拆分子问题，记住过往，减少重复计算。可以将动态规划理解为有限状态自动机或者有向无环图，每一个节点代表一个状态，任何一个非起始节点都可以从其他节点转移过来称为状态转移。当前求解的过程中参考了以前求解过的问题的结果，这个过程不能形成回路，形成回路就无法求解。动态规划求解步骤：
1. 设计状态，确定状态含义 2. 确定状态转移方程 3. 确定初始状态 4. 执行状态转移 5. 计算最终的解

常见题型：

0070-爬楼梯
1342-将数字变成 0 的操作次数
0746-使用最小花费爬楼梯
0198-打家劫舍
0213-打家劫舍 II
0091-解码方法
1646-获取生成数组中的最大值
1043-分隔数组以得到最大和
139-单词拆分
1869-哪种连续子字符串更长
724-寻找数组的中心下标
221-最大正方形
1277-统计全为 1 的正方形子矩阵
256-粉刷房子 LCR 091. 粉刷房子
53-最大子数组和
300-最长递增子序列
673-最长递增子序列的个数
1027-最长等差数列
873-最长的斐波那契子序列的长度
516-最长回文子序列
1143-最长公共子序列
72-编辑距离
118-杨辉三角
62-不同路径
64-最小路径和
121-买卖股票的最佳时机
122-买卖股票的最佳时机 II
123-买卖股票的最佳时机 III
188-买卖股票的最佳时机 IV
309-买卖股票的最佳时机含冷冻期
714-买卖股票的最佳时机含手续费
416-分割等和子集

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。相同问题：70-爬楼梯通用公式为: f(n) = f(n-1) + f(n-2) 当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2; 当只有1级台阶时，只有一种跳法，即f(1) = 1；描述为有向无环图如下所示：

若使用递归方法实现，将由很多重复节点计算：

int numWays(int n) 
{
    if(n == 1){return 1;}
    if(n == 2){return 2;}
    return numWays(n-1) + numWays(n-2);
}

使用动态规划实现，减少重复计算：

int numWays(int n) 
{
    if (n <= 1) {return 1;}
    if (n == 2) {return 2;}
    int a = 1;
    int b = 2;
    int c = 0;
    for (int i = 3; i <= n; i++) {
        c = (a + b)% 1000000007;
        a = b;
        b = c;
    }
    return c;
}

70-爬楼梯:

int climbStairs(int n) 
{
    if(n <= 2){return n;}
    // f(n) = f(n - 1) + f(n - 2)
    int a = 1, b = 2, c = 0;
    for(int pos = 2; pos < n; pos ++){
        c = a + b;
        a = b;b = c;
    }
    return c;
}

贪心算法（Greedy Algorithm）

贪心算法参考算法导论第16章，

300-最长递增子序列

常见问题解析

股票问题：

参考 https://leetcode.cn/circle/discuss/qiAgHn/
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费

符号： * 用 n 表示股票价格数组的长度； * 用 i 表示第 i 天（i 的取值范围是 0 到 n - 1）； * 用 k 表示允许的最大交易次数； * 用 T[i][k] 表示在第 i 天结束时，最多进行 k 次交易的情况下可以获得的最大收益。

基准情况是显而易见的：T[-1][k] = T[i][0] = 0，表示没有进行股票交易时没有收益（注意第一天对应 i = 0，因此 i = -1 表示没有股票交易）。

基准情况：

T[-1][k][0] = 0, T[-1][k][1] = -Infinity   
T[i][0][0] = 0, T[i][0][1] = -Infinity

状态转移方程：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])   
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i])

情况一：k = 1

T[i][1][0] = max(T[i - 1][1][0], T[i - 1][1][1] + prices[i])   
T[i][1][1] = max(T[i - 1][1][1], T[i - 1][0][0] - prices[i]) = max(T[i - 1][1][1], -prices[i])

第二个状态转移方程利用了 T[i][0][0] = 0。

情况二：k 为正无穷
如果 k 为正无穷，则 k 和 k - 1 可以看成是相同的，因此有 T[i - 1][k - 1][0] = T[i - 1][k][0] 和 T[i - 1][k - 1][1] = T[i - 1][k][1]。每天仍有两个未知变量：T[i][k][0] 和 T[i][k][1]，其中 k 为正无穷，状态转移方程如下：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])   
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i]) = max(T[i - 1][k][1], T[i - 1][k][0] - prices[i])

情况三：k = 2
情况三和情况一相似，区别之处是，对于情况三，每天有四个未知变量：T[i][1][0]、T[i][1][1]、T[i][2][0]、T[i][2][1]，状态转移方程如下：

T[i][2][0] = max(T[i - 1][2][0], T[i - 1][2][1] + prices[i])   
T[i][2][1] = max(T[i - 1][2][1], T[i - 1][1][0] - prices[i])   
T[i][1][0] = max(T[i - 1][1][0], T[i - 1][1][1] + prices[i])   
T[i][1][1] = max(T[i - 1][1][1], T[i - 1][0][0] - prices[i]) = max(T[i - 1][1][1], -prices[i])

第四个状态转移方程利用了 T[i][0][0] = 0。

情况四：k 为任意值
问题等价于情况二。

情况五：k 为正无穷但有冷却时间
但是在有「冷却时间」的情况下，如果在第 i - 1 天卖出了股票，就不能在第 i 天买入股票。因此，如果要在第 i 天买入股票，第二个状态转移方程中就不能使用 T[i - 1][k][0]，而应该使用 T[i - 2][k][0]。状态转移方程中的别的项保持不变，新的状态转移方程如下：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])   
T[i][k][1] = max(T[i - 1][k][1], T[i - 2][k][0] - prices[i])

情况六：k 为正无穷但有手续费
由于需要对每次交易付手续费，因此在每次买入或卖出股票之后的收益需要扣除手续费，新的状态转移方程有两种表示方法。
第一种表示方法，在每次买入股票时扣除手续费：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])   
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k][0] - prices[i] - fee)

第二种表示方法，在每次卖出股票时扣除手续费：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i] - fee)   
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k][0] - prices[i])

状态转移理解：

对于状态转移方程中的 T[i][k][0]，第 i 天进行的操作只能是休息或卖出，因为在第 i 天结束时持有的股票数量是 0。T[i - 1][k][0] 是休息操作可以得到的最大收益，T[i - 1][k][1] + prices[i] 是卖出操作可以得到的最大收益。注意到允许的最大交易次数是不变的，因为每次交易包含两次成对的操作，买入和卖出。只有买入操作会改变允许的最大交易次数。

对于状态转移方程中的 T[i][k][1]，第 i 天进行的操作只能是休息或买入，因为在第 i 天结束时持有的股票数量是 1。T[i - 1][k][1] 是休息操作可以得到的最大收益，T[i - 1][k - 1][0] - prices[i] 是买入操作可以得到的最大收益。注意到允许的最大交易次数减少了一次，因为每次买入操作会使用一次交易。

为了得到最后一天结束时的最大收益，可以遍历股票价格数组，根据状态转移方程计算 T[i][k][0] 和 T[i][k][1] 的值。最终答案是 T[n - 1][k][0]，因为结束时持有 0 份股票的收益一定大于持有 1 份股票的收益。

前缀和

最长递增子序列

https://writings.sh/post/longest-increasing-subsequence-revisited

斐波那契数列

https://leetcode.cn/problems/fibonacci-number/solutions/545049/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

Reference

[0] https://github.com/krahets/hello-algo
[1] https://www.hello-algo.com/
[2] https://www.programmercarl.com/
[3] https://leetcode.cn/problem-list/2cktkvj/