经典算法模版

动态规划 – 一维

By crabboss

今天看到“左神”有关动态规划的课程，瞬间觉得醍醐灌顶。

“左神”认为动态规划都可以从递归进行转移，无非动态规划是存储了递归过程中的中间变量，优化了递归用时。

以及大家都脑壳痛的动态规划转移方程如何得到：

  • 1 递归尝试
  • 2 见多识广

从递归->动态规划套路：

  • 1 手工进行尝试和推导，查看和总结规律
  • 2 尝试暴力递归
  • 3 从顶到底的动态规划：在暴力递归的基础上外挂缓存
    • dp数组中取数据
    • dp数组中存数据
  • 4 从底到顶的动态规划：抛弃暴力递归，直接从源头开始进行状态计算
    • 将ans和递归调用全部变成dp[i]
  • 5 空间压缩（从底到顶的动态规划基础上对递归数组进行空间压缩）
    • dp数组变成滚动的常数项个变量
    • dp[i] -> cur
    • next = dp[n], nextNext = dp[n+1] or prePre = dp[0], pre = dp[1]
    • return pre or return next

1 509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

1.1 手工尝试

0 1 1 2 3 5 8 13 21 ……

规律 : f(n) = f(n-2) + f(n-1)

1.2 暴力递归

class Solution {
public:
    int fib(int n) {
        if (n == 0 || n == 1) return n;
        return fib(n-2) + fib(n-1);
    }
};

1.3 从顶到底的动态规划

class Solution {
public:
    int f1(int n, vector& dp){
        if (n == 0 || n == 1) return n;
        // 1 如果递归结果在递推数组中，则直接返回
        if (dp[n] != -1)  return dp[n];
        // 2 通过递归得到递推结果
        int ans = f1(n-2, dp) + f1(n-1, dp);
        // 3 将递归结果存储到递推数组
        dp[n] = ans;
        return dp[n];
    }

    int fib(int n) {
        vector dp(n+1, -1);
        return f1(n, dp);
    }
};

1.4 从底到顶的动态规划

class Solution {
public:
    int fib(int n) {
        if (n==0 || n==1) return n;
        vector dp(n+1, -1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-2] + dp[i-1];
        }
        return dp[n];
    }
};

1.5 空间压缩

class Solution {
public:
    int fib(int n) {
        if (n==0 || n==1) return n;
        int prePre=0, pre=1;
        int cur;
        for(int i=2; i<=n; i++){
            cur = prePre + pre;
            prePre = pre;
            pre = cur;
        }
        return pre;
    }
};

2 983. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

  • 一张 为期一天 的通行证售价为 costs[0] 美元；
  • 一张 为期七天 的通行证售价为 costs[1] 美元；
  • 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

2.1 手工尝试

days  = [1, 4, 6, 7, 8, 20]

costs = [2, 7, 15]

f(x) : 从x天开始需要花费的最小金钱

f(x) = min({选择一天的cost+f(j) , 选择7天的cost+f(j), 选择30天的cost+f(j)})

f(0) = min({2 + f(1), 7+f(4), 15})

2.2 暴力递归

class Solution {
public:
    vector duration = {1, 7, 30};
    int f1(vector& days, vector& costs, int i){
        if (i == days.size()) return 0;
        int ans = INT_MAX;
        // i为当前day下标 j为下一个day下标 k为买什么票的下标
        for(int k=0, j=i; k<3; k++){
            while(j < days.size() && days[i]+duration[k] > days[j]) j++;
            ans = min(ans, costs[k] + f1(days, costs, j));
        }
        return ans;
    }

    int mincostTickets(vector& days, vector& costs) {
        int result = f1(days, costs, 0);
        return result;
    }
};

2.3 从顶到底的动态规划

class Solution {
public:
    vector duration = {1, 7, 30};
    int f1(vector& days, vector& costs, int i, vector& dp){
        if (i == days.size()) return 0;
        if (dp[i] != INT_MAX) return dp[i];
        int ans = INT_MAX;
        // i为当前day下标 j为下一个day下标 k为买什么票的下标
        for(int k=0, j=i; k<3; k++){
            while(j < days.size() && days[i]+duration[k] > days[j]) j++;
            ans = min(ans, costs[k] + f1(days, costs, j, dp));
        }
        dp[i] = ans;
        return ans;
    }

    int mincostTickets(vector& days, vector& costs) {
        vector dp(days.size()+1, INT_MAX);
        int result = f1(days, costs, 0, dp);
        return result;
    }
};

2.4 从底到顶的动态规划

class Solution {
public:
    vector duration = {1, 7, 30};

    int mincostTickets(vector& days, vector& costs) {
        vector dp(days.size()+1, INT_MAX);
        dp[days.size()] = 0;
        for(int i=days.size()-1; i>=0; i--){
            // i为当前day下标 j为下一个day下标 k为买什么票的下标
            for(int k=0, j=i; k<3; k++){
                while(j < days.size() && days[i]+duration[k] > days[j]) j++;
                dp[i] = min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }
};

2.5 空间压缩

由于f(j)中的j下一个元素的索引不固定，所以无法使用空间压缩。

3 91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

3.1 手工尝试

“1101”: f(0) = f(1) + f(2)

  • 1  101
  • 11  01

3.2 暴力递归

class Solution {
public:
    int f1(string s, int i){
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;
        int ans = f1(s, i+1);
        if (i+1 < s.size() && (s[i]-'0')*10 + (s[i+1]-'0') <= 26){
            ans += f1(s, i+2);
        }
        return ans;
    }

    int numDecodings(string s) {
        int result = f1(s, 0);
        return result;
    }
};

3.3 从顶到底的动态规划

class Solution {
public:
    int f1(string s, int i, vector& dp){
        if (i == s.size()) return 1;
        if (dp[i] != -1) return dp[i];
        if (s[i] == '0') return 0;
        int ans = f1(s, i+1, dp);
        if (i+1 < s.size() && (s[i]-'0')*10 + (s[i+1]-'0') <= 26){
            ans += f1(s, i+2, dp);
        }
        dp[i] = ans;
        return ans;
    }

    int numDecodings(string s) {
        vector dp(s.size()+1, -1);
        return f1(s, 0, dp);
    }
};

3.4 从底到顶的动态规划

class Solution {
public:

    int numDecodings(string s) {
        vector dp(s.size()+1, 0);
        dp[s.size()] = 1;
        for(int i=s.size()-1; i>=0; i--){
            if (s[i] == '0'){
                dp[i] = 0; continue;
            }
            dp[i] = dp[i+1];
            if (i+1 < s.size() && (s[i]-'0')*10 + (s[i+1]-'0') <= 26){
                dp[i] += dp[i+2];
            }
        }
        return dp[0];
    }
};

3.5 空间压缩

class Solution {
public:

    int numDecodings(string s) {
        int next=1, nextNext=0;
        int cur;
        for(int i=s.size()-1; i>=0; i--){
            if (s[i] == '0') cur = 0;
            else{
                cur = next;
                if (i+1 < s.size() && (s[i]-'0')*10 + (s[i+1]-'0') <= 26){
                    cur += nextNext;
                }
            }
            nextNext = next;
            next = cur;
        }
        return next;
    }
};

4 639. 解码方法 II

一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

  • "AAJF" 对应分组 (1 1 10 6)
  • "KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。

由于答案数目可能非常大，返回 109 + 7 的 模 。

4.1 手工尝试

4.2 暴力递归

4.3 从顶到底的动态规划

4.4 从底到顶的动态规划

4.5 空间压缩

5 264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector  dp(n+1, 0);
        dp[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        for(int i=2; i<=n; i++){
            dp[i] = min({2*dp[i2], 3*dp[i3], 5*dp[i5]});
            if (dp[i] == 2*dp[i2]) i2++;
            else if (dp[i] == 3*dp[i3]) i3++;
            else if (dp[i] == 5*dp[i5]) i5++;
            while (dp[i] == dp[i-1]){
                dp[i] = min({2*dp[i2], 3*dp[i3], 5*dp[i5]});
                if (dp[i] == 2*dp[i2]) i2++;
                else if (dp[i] == 3*dp[i3]) i3++;
                else if (dp[i] == 5*dp[i5]) i5++;
            }
        }
        return dp[n];
    }
};

6 32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s=="") return 0;
        int ans = 0;
        vector dp(s.size(), 0);
        for(int i=1; i<s.size(); i++){ if (s[i] == ')'){ int pre = i - dp[i-1] - 1; // 匹配的左括号的位置 if (pre >= 0 && s[pre] == '('){
                    int temp = pre-1>=0?dp[pre-1] : 0;
                    dp[i] = 2 + dp[i-1] + temp; 
                }
            }
            ans = max(dp[i], ans);
        }
        return ans;
    }
};

7 467. 环绕字符串中唯一的子字符串

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

  • "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

该题不是传统动态规划使用下标位置作为dp数组的索引，而是使用字符作为dp数组的索引。

dp[‘a’] ……

8 940. 不同的子序列 II

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

s = "abc"
all : {}, {a}
all : {}, {a}, {b}, {ab}
all : {}, {a}, {b}, {ab}, {c}, {ac}, {bc}, {abc}

s = "aba"
all : {}, {a}
all : {}, {a}, {b}, {ab}
all : {}, {a}, {b}, {ab}, {a}, {aa}, {ba}, {aba} -> {}, {a}, {b}, {ab}, {aa}, {ba}, {aba}

s = "aaa"
all : {}, {a}
all : {}, {a}, {a}, {aa} -> {}, {a},{aa}
all : {}, {a}, {aa}, {a}, {aa}, {aaa} -> {}, {a}, {aa}, {aaa}

核心在于纯新增字符 = all – 当前上次记录

all中包含空集合, 字符集合中包含空集合。

s = "aba"
eg: "ab" -> "aba"
new add is : all({}, {a}, {b}, {ab}) - a("a") = 3 而不是4

By crabboss

Related Post

经典算法模版

回溯篇 – 子集

crabboss
经典算法模版

回溯篇 – 全排列

crabboss
经典算法模版

回溯篇 – 组合

crabboss

You Missed

大模型 大模型基础

大模型分布式入门

大模型 大模型量化

大模型量化入门

大模型 大模型基础

优化器的进化之旅

大模型 大模型基础

FlashAttention – 原理解析