leetcode｜动态规划

本文最后更新于：4 years ago

在搞懂动态规划之前，我们有必要提一下，记忆化搜索和动态规划的区别，我们以斐波拉契数列求第n项为例。

记忆化搜索 —— 自顶向下的解决问题

假设基本的问题已经解决了，在基本问题的基础上，解决现有问题。

例：假设 Fib(n - 1) 和 Fib(n - 2) 已解决，来解决 Fib(n)。

/*
斐波拉契数列
O(n)
*/
long long Fib(int n, vector<long long> &a){ // 用 a 记录 Fib(1)、Fib(2)、Fib(3)...
    if (n == 1 || n == 2) {
        return 1;
    }
    if (a[n] == -1) {
        a[n] = Fib(n - 1, a) + Fib(n - 2, a);
        cout << n << endl;
    }
    return a[n];
}

int main(){
    int n = 100;
    vector<long long> a(n + 1, -1);
    cout << Fib(n, a) << endl;
    return 0;
}

动态规划 —— 自底而上的解决问题

先解决小数据量下的问题，再逐渐递增数据量。

例：先解决 Fib(3)、Fib(4) 等小数据量的问题，再递增到 Fib(n)。

/*
斐波拉契数列
O(n)
*/
int main(){
    int n = 100;
    vector<long long> a(n, -1);
    a[1] = 1;
    a[2] = 1;
    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2];
    }
    cout << a[n] << endl;
    return 0;
}

优化，因为只会用到 a[i - 1] 和 a[i - 2] 两个数，所以可以用滚动数组优化：

int main(){
    int n = 100;
    long long a = 1, b = 1, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        b = a;
        a = c;
        cout << i << endl;
    }
    cout << c << endl;
    return 0;
}

什么是动态规划

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一个，最终获得原问题的答案。【用记忆化搜索思考问题，再用动态规划实现（更简洁）】

graph TD
A(原问题问题) -->|拆解成| B(重叠子问题 - 最优子结构)
B --> C(递归问题)
C --> D(记忆化搜索--自顶向下)
C --> E(动态规划--自底向上)
D --> F((利于思考))
E --> G((实现简洁))

判断是否使用动态规划

一般询问的是最优解，并且其中含有重叠子问题。

动态规划的求解方式便是，求解重叠子问题的最优解，即最优子结构。

最优解问题

题目	关键字	方法
#746.使用最小花费爬楼梯	最小花费	min(F(i - 1), F(i - 2)) + cost[i]
#120. 三角形最小路径和	最小路径和	min(F[i - 1][j - 1], F[i - 1][j]) + cost[i][j]
#64. 最小路径和	最小路径和	min(F[i][j - 1], F[i - 1][j]) + cost[j]
#343. 整数拆分	最大乘积	max(F[i - j] * j, (i - j) * j, F[i]) 其中j∈{1, 2…i-2, i-1}
#279. 完全平方数	最少个数	min(F[i - j * j]+1, F[i]) 其中j * j >= i
198. 打家劫舍	最高金额	max(F(i - 1), F(i - 2) + current[i])
#213. 打家劫舍 II	最高金额	max(不偷最后一家，不偷第一家)
#337. 打家劫舍 III	最高金额	max(偷父节点，不偷父节点)
#121. 买卖股票的最佳时机	最大收益
#121. 买卖股票的最佳时机 II	最大收益	max(倒数第3天卖，倒数第3天不卖)
#309. 最佳买卖股票时机含冷冻期	最大收益	max(倒数第4天卖，倒数第4天不卖)
#53. 最大子序和	最大和	ans = max(ans+num[i], num[i]) max_ans = max(当前ans，max_ans)

多少种可能性（最多的可能性）

也是最优解问题，因为每次选择都要选择最多可能性的方法。
类似于斐波拉契数列Fibonacci。

题目	关键字	方法
#70. 爬楼梯	多少种方法	F(i - 1) + F(i - 2)
#91. 解码方法	多少种方法	F(i - 2) + F( i - 1)
#62. 不同路径	多少种路径	F[i - 1][j] + F[i][j - 1]
#63. 不同路径II	多少种路径	F[i - 1][j] + F[i][j - 1]

#70. 爬楼梯

传送门：#70. 爬楼梯

1.记忆化搜索

n阶楼梯的可能性 = n-1阶楼梯的可能性 + n-2阶楼梯的可能性。

long long fun(int n, vector<long long> &num){    // 用数组num储存每阶台阶的可能性
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (num[n] == -1) {
        num[n] = fun(n - 1, num) + fun(n - 2, num);
    }
    return num[n];
}

int main(){
    int n = 10;
    vector<long long> num(n+1, -1);
    cout << fun(n, num) << endl;
    return 0;
}

2.动态规划

1 阶楼梯的可能性 + 2 阶楼梯的可能性 = 3 阶楼梯的可能性。

从 1阶楼梯、2阶楼梯开始递推至 n阶。并用滚动数组记录需要用到的两个值，i-1阶、i-2阶。

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

#746.使用最小花费爬楼梯

传送门：#746.使用最小花费爬楼梯
本题特殊的地方，cost = [10, 15, 20]，其实一共要上 4 阶，[10, 15, 20, 0]，第 4 阶为顶层，花费为 0；
因为，从 15 一次跨两阶可以到顶层。

1.记忆化搜索

第 i 阶的最小花费 = min(第 i-1 阶的最小花费，第 i-2 阶的最小花费) + 第 i 阶的费用 cost[i]

int DP(vector<int> &cost, int i, vector<int> &memo){
    if (i == 0 || i == 1) {
        memo[i] = cost[i];
    }
    if (memo[i] == -1) {
        memo[i] = min(DP(cost, i - 1, memo), DP(cost, i - 2, memo)) + cost[i];
        cout << i << " = " << memo[i] << endl;
    }
    return memo[i];
}

int minCostClimbingStairs(vector<int> &cost) {
    cost.push_back(0);
    int size = cost.size();
    vector<int> memo(size, -1);
    return DP(cost, size - 1, memo);
}

2.动态规划

先计算第 1 阶和第 2 阶的最小花费，由此计算第 3 阶的最小花费；由第 2 阶和第 3 阶的最小花费计算第 4 阶的最小花费…由此递推到第 n 阶。

int minCostClimbingStairs(vector<int> &cost) {
    cost.push_back(0);
    int dp_1 = cost[0], dp_2 = cost[1], dp_3 = 0;
    for (int i = 2; i < cost.size(); i++) {
        dp_3 = min(dp_1, dp_2) + cost[i];
        dp_1 = dp_2;
        dp_2 = dp_3;
    }
    return dp_3;
}

#120. 三角形最小路径和

传送门：#120. 三角形最小路径和

1.记忆化搜索

一共有 size 层，假设从顶层到 size-2 层的每一个点的最小路径和都知道。以此为基础计算从顶层到 size-1 层的每一个点的最小路径和。

/*
执行用时：8 ms, 在所有 C++ 提交中击败了92.89%的用户
内存消耗：9 MB, 在所有 C++ 提交中击败了
100.00%的用户
*/

int MinNum(vector<vector<int> >& triangle, int i, int j, vector<vector<int> > &memo){
      /*
      将到每个点最小路径和储存在二维数组 memo 中。
      从底向上递归，搜索每个点的 memo[i][j]。
      */
    if (i == 0) {
        memo[i][0] = triangle[i][0];     
    } else if (memo[i][j] == 0x3f3f3f3f && j > 0 && j < i) {
        memo[i][j] = min(MinNum(triangle, i - 1, j - 1, memo), 
                                    MinNum(triangle, i - 1, j, memo)) + triangle[i][j];         
    } else if (memo[i][j] == 0x3f3f3f3f && j == 0) {
        memo[i][j] = MinNum(triangle, i - 1, j, memo) + triangle[i][j];
    } else if (memo[i][j] == 0x3f3f3f3f && j == i) {
        memo[i][j] = MinNum(triangle, i - 1, j - 1, memo) + triangle[i][j];
    }
    return memo[i][j];
}

int minimumTotal(vector<vector<int> >& triangle){
    int size = triangle.size();
      // 数组 memo 用来储存到每个点最小路径和。
    vector<vector<int> > memo(size, vector<int>(size, 0x3f3f3f3f));
      // 将最后一行的点的最小路径和储存在 min_num 中，并查找 min_num 的最小值。
      vector<int> min_num;
    for (int i = 0; i < size; i++) {
        min_num.push_back(MinNum(triangle, triangle.size()-1, i, memo));   
    }
    int min_ans = min_num[0];
    for (int i = 1; i < min_num.size(); i++) {
        if (min_num[i] < min_ans) {
            min_ans = min_num[i];
        }
    }
    return min_ans;
}

2.动态规划

从第 0 层开始，计算第 1 层的每个点的最小路径和，以第 1 层为基础，计算第 2 层的每个点的最小路径和，以此类推，并将这些最小路径和储存在数组 memo 中。

下列代码可以优化成用一维数组 memo 记录上一行的最小路径，因为计算当前行各个数的最小路径，只需要知道上一层的最小路径就可以。

/*
执行用时：8 ms, 在所有 C++ 提交中击败了92.89%的用户
内存消耗：8.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/
int minimumTotal(vector<vector<int> >& triangle){
    int size = triangle.size();
    // 将到每个点最小路径和储存在二维数组 memo 中。
    vector<vector<int> > min_num(size, vector<int>(size, 0x3f3f3f3f));
    for (int i = 0; i < size; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == 0) {
                min_num[i][j] = triangle[0][0];
            } else if (j == 0) {
                min_num[i][j] = min_num[i - 1][j] + triangle[i][j];
            } else if (j == i) {
                min_num[i][j] = min_num[i - 1][j - 1] + triangle[i][j];
            } else {
                min_num[i][j] = min(min_num[i - 1][j], min_num[i - 1][j - 1]) 
                                              + triangle[i][j];
            }
        }
    }
    int min_ans = min_num[size - 1][0];
    for (int i = 1; i < min_num[size - 1].size(); i++) {
        if (min_num[size - 1][i] < min_ans) {
            min_ans = min_num[size - 1][i];
        }
    }
    return min_ans;
}

其实我们发现，将计算第 i 层各点的最小路径和时，只需要知道第 i-1 层各点的最小路径和。所以我们只需要用一个 size 大小的数组，储存第 i-1 层的各层的最小路径和，并不需要用 size * size 大小的二维数组，储存所有点的最小路径和。

虽然以上的方法节省了空间，但是相对应的时间也会更长。用空间换时间还算划算。

#64. 最小路径和

传送门：#64. 最小路径和

1.动态规划

这道题和 #120. 三角形最小路径和思路十分相似，直接自顶向下用动态规划写了。

下列代码可以优化成用一维数组 memo 记录上一行的最小路径，因为计算当前行各个数的最小路径，只需要知道上一层的最小路径就可以。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int size = grid.size();
        if (size == 0) {
            return 0;
        }
        int row = grid[0].size();
        // 用数组 memo 储存到每个点的最小路径和。
        vector<vector<int> > memo(size, vector<int>(row, 0x3f3f3f3f));      
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < row; j++) {
                if (i == 0 && j == 0) {
                    memo[i][j] = grid[0][0];
                } else if (j == 0) {
                    memo[i][j] = memo[i - 1][j] + grid[i][j];
                } else if (i == 0) {
                    memo[i][j] = memo[i][j - 1] + grid[i][j];
                } else {
                    memo[i][j] = min(memo[i][j - 1], memo[i - 1][j]) + grid[i][j];
                }    
            }
        }
        return memo[size - 1][row - 1];
    }
};

#343. 整数拆分

传送门：#343. 整数拆分

1.记忆化搜索

n的最大拆分 = max( 1*[n-1]的最大拆分，1*[n-1]，2*[n-2]的最大拆分，2*[n-2]…[n-1]*1的最大拆分，[n-1]*1)。

其中，我将 max(i*[n-i]的最大拆分，i*[n-i]) 存入 memo[n] 中，并下一个循环中，比较出 max(i*[n-i]的最大拆分，i*[n-i]，memo[n])。

vector<int> memo;

int Max3(int a, int b, int c){
    return max(a, max(b, c));
}

int MaxBreak(int n){
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    for (int i = 1; i <= n; i++) {
        memo[n] = Max3(i * MaxBreak(n - i), i * (n - i), memo[n]);
    }
    return memo[n];
}

int integerBreak(int n) {
    memo = vector<int>(n + 1, -1);
    return MaxBreak(n);
}

2.动态规划

n的最大拆分 = max( 1*[n-1]的最大拆分，1*[n-1]，2*[n-2]的最大拆分，2*[n-2]…[n-1]*1的最大拆分，[n-1]*1)。

我们自底向上，从 1 计算到 n的最大拆分。

1的最大拆分 = 1；

2的最大拆分 = max(1*[2-1]的最大拆分，1*[2-1])；

3的最大拆分 = max(1*[3-1]的最大拆分，1*[3-1]，2*[3-2]的最大拆分，2*[3-2])

其中，我将 max(1*[3-1]的最大拆分，1*[3-1]) 存入 memo[3] 中，并下一个循环中，比较出 max(2*[3-2]的最大拆分，2*[3-2]，memo[3])。

int Max3(int a, int b, int c){
    return max(a, max(b, c));
}

int integerBreak(int n) {
    // 用数组 memo 储存从 1 到 n 的最大拆分乘积。
    vector<int> memo(n + 1, -1);
    memo[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            // 关键的递推公式
            memo[i] = Max3(j * memo[i - j], j * (i - j), memo[i]);
        }
    }
    return memo[n];
}

#279. 完全平方数

传送门：#279. 完全平方数

1.动态规划

自底向上分析，（为方便表述，拆分成完全平方数，最少个数表示为 F），

F1 = 1；（1 为完全平方数）

F2 = 2；（F2 = F1 + F1）

F3 = 3；（F3 = F2 + F1）

F4 = 1；（4 本身是完全平方数，故 F4 = 1）

F5 = 2；（F5 = （F4 + F1）

F6 = 3；（F6 = min（（F5 + F1），（F4 + F2））

…

每次拆解，n - 一个完全平方数A = 另外一个数B；另外一个数B - 一个完全平方数C = 另外一个数D…

via：leetcode题解中的一个图，和我想法一致。（其中 F1、F4、F9…等完全平方数的最少个数等于 1，图中用 +1表示） numSquares

int numSquares(int n) {
    vector<int> min_num(n + 1, 0x7fffffff);
    min_num[0] = 0;
    min_num[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; i - j * j >= 0; j++) {
            min_num[i] = min(min_num[i - j * j] + 1, min_num[i]);
        }
    }
    return min_num[n];
}

#91. 解码方法

传送门：#91. 解码方法
**PS：**此题有些特殊的数据需要注意，“0”、“00”、“100”、“01”，应处理好边界判断的问题。

1.深度优先搜索

以 1234 为例，如下图，

先深入左子树， 1、2、3、4 递归到底，成功；

再返回 2，进入 34，非法；

再返回 1，继续递归至 23、4，成功；

再返回开始，递归右子树，12、3、4，成功；

再返回 12，进入 34，非法。

深搜完成。

graph TD
A(开始) --> B(1)
B --> C(2)
C --> D(3)
D --> E(4)
E --> P((成功))
A --> F(12)
B --> G(23)
G --> O(4)
O --> Q((成功))
C --> K(34)
K --> S((非法))
F --> L(3)
F --> M(34)
M --> T((非法))
L --> N(4)
N --> R((成功))

虽然思路极其简单清晰，在本地IDE也可以AC，但是递归压栈过多，数据规模稍大就会超时。

int num = 0;
void dfs(string s, int index, int n){
    if (index == n) {   // 递归退出条件
        num++;
        return;
    }
    if (s[index + 1] != '0') {
        dfs(s, index + 1, n);    // 1个数字单独解码，也就是遍历index节点的左子树
        if (index + 2 <= n && (s[index + 1] - '0') < 3 
            && (s[index + 1] - '0') * 10 + (s[index + 2] - '0') <= 26) {
            dfs(s, index + 2, n);   // 2个数字合并解码，也就是遍历index节点的右子树
        }
    }
    return;
}

int numDecodings(string s) {
    int n = s.length() - 1;
    dfs(s, -1, n);
    return num;
}

2.动态规划

以1224为例，字符串的解码方式数量用 F 表示，

F(“1”) = 1

F(“12”) = F(“1”) + F(“”)

F(“122”) = F(“12”) + F(“1”)

F(“1221”) = F(“122”) + F(“12”)

…

以 F(“1221”) 为例，让尾数1单独解码的方式数量为 F(“122”)，让 1 和前面的 2 合并解码方式数量为 F(“12”)。

int numDecodings(string s) {
    if (s[0] == '0') {
        return 0;
    }
    s = '0' + s;   // 此处为了解决 F("") = 1 的问题
    int n = s.length();
    vector<int> memo(n, 0);
    memo[0] = 1;   // 此处为了解决 F("") = 1 的问题
    memo[1] = 1;
    for (int i = 2; i < n; i++) {
        if (s[i] != '0') {
            memo[i] += memo[i - 1];
        }
        if (s[i - 1] != '0' && s[i - 1] - '0' < 3) {
            if (s[i - 1] - '0' < 2 || s[i] - '0' < 7) {
                memo[i] += memo[i - 2];
            }
        }
    }
    return memo[n - 1];
}

#62. 不同路径

传送门：#62. 不同路径
PS：对于m*n矩形，用二维数组表示为 memo[n][m]，n 表示行。

1.动态规划

从左上角开始，从左到右、从上至下的遍历，记录到达每一个点的不同路径的数量，并放在 memo 二维数组中记录，以此计算出右下角的点的值。

以下视频引用于leetcode题解，简单易通。

int uniquePaths(int m, int n) {
    vector<vector<int> > memo(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0) {
                memo[i][j] = 1;
            } else {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
            }
        }
    }
    return memo[n - 1][m - 1];
}

2.优化

优化前：
执行用时：4 ms, 在所有 C++ 提交中击败了30.17%的用户
内存消耗：6.4 MB, 在所有 C++ 提交中击败了100.00%的用户
优化后：
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了100.00%的用户

当计算第3行第4个点（3, 4）时，只需要知道（3, 3）和（2, 4）。

所以，当计算第3行时，只需要知道第2行的所有值就行。

故我们使用一维数组 memo 来记录 i-1 行的值。

int uniquePaths(int m, int n) {
    vector<int> memo(m, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0) {
                memo[j] = 1;
            } else {
                memo[j] = memo[j] + memo[j - 1];
            }
        }
    }
    return memo[m - 1];
}

#63. 不同路径II

传送门：#63. 不同路径II
PS：这题需要判断条件过多，使用一维数组可能会超时；建议空间换时间，使用二维数组。

1.动态规划

在 #62. 不同路径的基础上，增加判断 if (obstacleGrid[0][i] == 0) 。

需要注意的是，当第1行或者第1列出现 1的时候，1之后的点，memo 值 = 0；

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if (obstacleGrid[0][0] == 1) {
        return 0;
    }
    int n = obstacleGrid.size();
    int m = obstacleGrid[0].size();
    vector<vector<int> > memo(n, vector<int>(m, 0));
    for (int i = 0; i < m; i++) {      // 先处理第一行的值
        if (obstacleGrid[0][i] == 0) {
            memo[0][i] = 1;
        } else {
            break;   // 出现 1，其后的点的 memo = 0
        }
    }
    for (int i = 1; i < n; i++) {     // 再处理第一列的值
        if (obstacleGrid[i][0] == 0) {
            memo[i][0] = 1;
        } else {
            break;   // 出现 1，其后的点的 memo = 0
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (obstacleGrid[i][j] == 0) {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
            }
        }   
    }
    return memo[n - 1][m - 1];
}

#198. 打家劫舍

传送门：#198. 打家劫舍

1.动态规划

先求出只有1栋房子的最大金额memo[0]，再求出只有2栋房子的最大金额memo[1]，有3栋房子的最大金额为 max（memo[0] + nums[2], memo[1]）。

int rob(vector<int>& nums) {
    int size = nums.size();
    if (size == 0) {
        return 0;
    }
    if (size == 1) {
        return nums[0];
    }
    if (size == 2) {
        return max(nums[0], nums[1]);
    }
    vector<int> memo(size, -1);    // memo[i] 表示前i-1栋房子，能偷到的最大金额
    memo[0] = nums[0];
    memo[1] = max(nums[0], nums[1]);
    for (int i =2; i < size; i++) {
        memo[i] = max((memo[i - 2] + nums[i]), memo[i - 1]);
    }
    return memo[size - 1];
}

#213. 打家劫舍 II

传送门：#213. 打家劫舍 II

1.动态规划

环形问题，第一个和最后一个不能同时偷窃。所以我们有两种选择：

不偷最后一个房子，偷第 1 个房子到第 n-1 个房子，记为 [1, n - 1] 。
不偷第一个房子，偷第 2 个房子到第 n 个房子，记为 [2, n]。

所以在 #198. 打家劫舍的基础上，我只需计算 [1, n - 1] 的最大金额、[2, n] 的最大金额，二者中的最大的值便是所求。

在细节上，我们用数组 memo_1 储存 [1, n - 1] 中的最优子结构；用 memo_2 储存 [2, n] 中的最优子结构。在求 [2, n] 的最大金额过程中，我们只需设 memo[1] = 0 即可，也就代表只有一个房子的时候，最大金额等于0，也就是不偷第一个房子的意思。

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return nums[0];
    }
    vector<int> memo_1(n+1, 0);
    vector<int> memo_2(n+1, 0);
    // 求解memo_1[n - 1]
    memo_1[0] = 0;
    memo_1[1] = nums[0];
    memo_1[2] = max(nums[0], nums[1]);
    for (int i = 3; i <= n - 1; i++) {
        memo_1[i] = max(memo_1[i - 1], memo_1[i - 2] + nums[i - 1]);
    }
    // 求解memo_2[n]
    memo_2[0] = 0;
    memo_2[1] = 0;
    memo_2[2] = nums[1];
    for (int i = 3; i <= n; i++) {
        memo_2[i] = max(memo_2[i - 1], memo_2[i - 2] + nums[i - 1]);
    }

    return max(memo_2[n], memo_1[n - 1]);
}

#337. 打家劫舍 III

传送门：#337. 打家劫舍 III

1.暴力递归

方案一（偷父节点）：父节点的值 + 左儿子的左儿子最大金额 + 左儿子的右儿子最大金额 + 右儿子的左儿子的最大金额 + 右儿子的右儿子的最大金额
方案二（不偷父节点）：左儿子的最大金额 + 右儿子的最大金额

取方案一和方案二的最大值，为父节点的最大金额。

一图胜千言：

int rob(TreeNode* root) {
    if(root == NULL) {
        return 0;
    }
    int sum = root->val;
    if (root->left != NULL) {
        sum += rob(root->left->left) + rob(root->left->right);
    }
    if (root->right != NULL) {
        sum += rob(root->right->left) + rob(root->right->right);
    }
    return max(sum, rob(root->right) + rob(root->left));
}

2.记忆化搜索

减少递归次数，将每一个节点的最大金额，保存在哈希表（字典）中。（线性结构使用数组做备忘录，树状结构使用哈希表做备忘录）

unordered_map<TreeNode*,int> hash;     // 注意：键是指针，不是节点。
int rob(TreeNode* root) {
    if(root == NULL) {
        return 0;
    }
    if (hash.count(root) == 1) {
        return hash[root];
    }
    int sum = root->val;
    if (root->left != NULL) {
        sum += rob(root->left->left) + rob(root->left->right);
    }
    if (root->right != NULL) {
        sum += rob(root->right->left) + rob(root->right->right);
    }
    hash[root] = max(sum, rob(root->right) + rob(root->left));
    return hash[root];
}

#121. 买卖股票的最佳时机

传送门：#121. 买卖股票的最佳时机

1.动态规划

这题比较简单，为后面做铺垫。

max_rofit[i] = max(max_rofit[i - 1], prices[i] - min_prices)

min_prices = min(min, prices[i])

int maxProfit(vector<int>& prices) {
    const int n = prices.size();
    if (n == 0) {
        return 0;
    }
    int min = prices[0];
    int res = 0;
    for (int i = 1; i < n; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else {
            res = max(prices[i] - min, res);
        }
    }
    return res;
}

#122. 买卖股票的最佳时机 II

传送门：#121. 买卖股票的最佳时机 II

先总结一下，递推：max(倒数第二天买的情况，倒数第二天不买的情况)。

再具体来看，我们先想象一个普通的场景：[1, 2, 3, 4]，股票一直涨。

前 i 个元素的最大利润 = 前 i - 1 个元素的最大利润 + 当前元素的价格 prices[i - 1] - 前一个元素的价格 prices[i - 2] （倒数第二天买的情况）。

当然了股票跌的可能性：[1, 4, 3, 2]。

如果 当前元素的价格 prices[i - 1] < 前一个元素的价格 prices[i - 2]。前 i 个元素的最大利润 = 前 i - 1 个元素的最大利润（倒数第二天不买的情况）。

int maxProfit(vector<int>& prices) {
       int n = prices.size();
       if (n < 2) {
           return 0;
       }
       vector<int> memo(n + 1, 0);
       memo[0] = 0;
       memo[1] = 0;
       for (int i = 2; i <= n; i++) {
           memo[i] = prices[i - 1] > prices[i -2] ? memo[i - 1] + prices[i - 1] - prices[i - 2] : memo[i - 1];
       }
       return memo[n];
   }

#309. 最佳买卖股票时机含冷冻期

传送门：#309. 最佳买卖股票时机含冷冻期

记录前 i-1 天的最大值为 key。

graph TD
A(第 i 天的最大利润) --> B(第 i 天价格 是否 大于 key)
B -->|是| C(比较两种情况)
B -->|否| D(第 i 天最大利润 = 第 i-1 天最大利润)
C --> E(第 i-1 天最大利润 + 第 i 天价格 - key)
C --> F(第 i-3 天最大利润 + 第 i 天价格 - 第 i - 1天价格)
E --> G(二者取最大值)
F --> G

**第 i-1 天最大利润 + 第 i 天价格 - key：**这种情况是股票一直涨的情况，所以只需要一直加差价就可以了。比如：[1, 2, 3, 4, 5, 6]。
**第 i-3 天最大利润 + 第 i 天价格 - 第 i - 1天价格：**这种情况是中间有几天暴跌，适合先卖出股票，再低价买回来，赚取差价。比如：[2, 7, 1, 1, 7]。
为什么要取第 i-3 天最大利润呢？因为有冷冻期，卖出股票不可以第二天立马买股票，要隔一天。
**第 i 天最大利润 = 第 i-1 天最大利润：**比如：[1, 9, 1, 1]，第 3 天的收入 = 第 2 天的收入。

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
        return 0;
    }
    if (n == 2) {
        return prices[1] > prices[0] ? prices[1] - prices[0] : 0;
    }
    int key = 0;
    vector<int> memo(n + 1, 0); // memo[i] 表示第 i 天的最大收益
    memo[0] = 0;
    memo[1] = 0;
    if (prices[1] > prices[0]) {
        memo[2] = prices[1] - prices[0];
        key = prices[1];
    } else {
        memo[2] = 0;
        key = prices[0];
    }
    for (int i = 3; i <= n; i++) {
        if (prices[i - 1] > key) {
            // 第 i-1 天最大利润 + 第 i 天价格 - 前 i-1 天的最大值
            memo[i] = memo[i - 1] + prices[i - 1] - key;
            key = prices[i - 1];
        } else {
            memo[i] = memo[i - 1];
        }
          // 第 i-3 天最大利润 + 第 i 天价格 - 前 i-1 天的价格
        int tmp = memo[i - 3] + prices[i - 1] - prices[i - 2];
        if (tmp > memo[i]) {
            key = prices[i - 1];
            memo[i] = tmp;
        }
    }
    return memo[n];
}

#53. 最大子序和

传送门：#53. 最大子序和

用 ans 表示以 nums[i] 为结尾的最大序列和。

以 nums[i] 为结尾的最大序列和，要么是 nums[i]，要么是 num[i - 1] 的 ans + num[i]。

最后返回的答案也是在 n 个 ans 中选出最大值。

int maxSubArray(vector<int>& nums) {
    int n = nums.size(), ans = 0, max_ans = nums[0];
    for (int i = 0; i < n; i++) {
        ans = max(ans + nums[i], nums[i]);
        max_ans = max(max_ans, ans);
    }
    return max_ans;
}

#LCP 19. 秋叶收藏集

传送门：LCP 19.秋叶收藏集

这道题非常特别！

使用三个数组，dp[i][0]、dp[i][1]、dp[i][2] 。

dp[i][0]：前 i + 1 个元素，全是红，比如 rrrrr，最少需要多少次调整。
dp[i][1]：前 i + 1 个元素，满足前面是红，后面是黄，比如 rrrryyyy，最少需要多少次调整。
dp[i][2]：前 i + 1 个元素，满足前面后面是红，中间是黄，比如 rrryyyrrr，最少需要多少次调整。

状态转移关系：

dp[i][0] 等于 dp[i - 1][0] + 最后一个元素是不是红色。
dp[i][0] = dp[i - 1][0] + (leaves[i] == 'r' ? 0 : 1)
dp[i][1] 等于 min( dp[i - 1][0] + 最后一个元素是不是黄色，dp[i - 1][1] + 最后一个元素是不是黄色 )。
dp[i][1] = min(dp[i - 1][1] + (leaves[i] == 'y' ? 0 : 1), dp[i - 1][0] + (leaves[i] == 'y' ? 0 : 1));
dp[i][2] 等于 min( dp[i - 1][1] + 最后一个元素是不是红色，dp[i - 1][2] + 最后一个元素是不是红色 )。
dp[i][2] = min(dp[i - 1][1] + (leaves[i] == 'r' ? 0 : 1), dp[i - 1][2] + (leaves[i] == 'r' ? 0 : 1));

PS：注意 pd 初始状态。

class Solution {
public:
    int minimumOperations(string leaves) {
        int leaves_size = leaves.size();
        vector< vector<int> > dp(leaves_size, vector<int>(3, 0));
        for (int i = 0; i < leaves_size; i++) {
            // 红
            if (i < 1) {
                dp[i][0] = (leaves[i] == 'r' ? 0 : 1);
            } else {
                dp[i][0] = dp[i - 1][0] + (leaves[i] == 'r' ? 0 : 1);
            }
            
            // 红黄
            if (i < 1) {
                dp[i][1] = dp[i][0];
            } else {
                dp[i][1] = min(dp[i - 1][1] + (leaves[i] == 'y' ? 0 : 1), dp[i - 1][0] + (leaves[i] == 'y' ? 0 : 1));
            }

            // 红黄红
            if (i < 2) {
                dp[i][2] = dp[i][1];
            } else {
                dp[i][2] = min(dp[i - 1][1] + (leaves[i] == 'r' ? 0 : 1), dp[i - 1][2] + (leaves[i] == 'r' ? 0 : 1));
            }
        }
        return dp[leaves_size - 1][2];
    }
};

Mark

#算法 #LeetCode #动态规划

leetcode｜动态规划

https://www.aimtao.net/dynamic-programming/

Posted on

2020-07-11

Licensed under

学习笔记｜算法 Previous

编程中的正无穷大和 memset 的原理 Next