腾讯

昨天腾讯公布了 2025 年第二季度的业绩报告。

就还是那只鹅，就还是那个超预期。

总营收 1845 亿，同比增长 15%；净利润 556.3 亿，同比增长 17%；经营利润 692.5 亿，同比增长 18%。

这里面最炸裂的，是毛利率从去年的 53% 提升至 57%，盈利能力显著增强。

这里面，最大的功劳，除了雷打不动的"长青游戏”战略（新游戏《三角洲行动》表现强劲），还有的就是 AI 赋能。

腾讯将 AI 应用于广告的创作、投放、推荐和效果分析，有效提升了广告的点击率、转化率和广告主的投入回报率。

这财报一出，可以说流水的 AI，铁打的腾讯。

多少公司，还在卷大模型参数，卷快速迭代，这从行业发展来看，当然是对的。

但从商业角度（或者资本角度）来看，通常意味着"暂看不出来盈利点"的无底洞烧钱策略。

但腾讯这边已经开始用 AI 落地盈利了，你永远可以相信腾讯的"后手策略"。

还记得早期，各大公司都在堆参数搞大模型，唯独腾讯迟迟没有做大投入，导致一度被外界预言会在 AI 时代落后。之后 DeepSeek-R1 爆火，腾讯元宝直接通过"点外卖"（接入 DS 开源模型），就做到了全国 AI 应用头号位置。

更加凡尔赛的是，腾讯利用 AI 赋能广告这事儿，还是在当前腾讯短视频广告加载率只有 3%~6% 的情况下发生的，而行业领先水平大概是 13%~16%。

也就是腾讯目前仅用了很少一部分的变现能力 + AI，就赚到了大钱。

这才是理想中的科技公司：有极宽的护城河、具备规模化生产能力、能够运用技术手段来提升利润。

啥别说了，今年的校招策略，还是和去年、前年，大前年一样，有鹅选鹅。

...

回归主题。

来一道和「腾讯」相关的算法题。

题目描述

平台：LeetCode

题号：940

给定一个字符串 s，计算 s 的不同非空子序列的个数。

因为结果可能很大，所以返回答案需要对取余。

字符串的子序列是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"

输出：7

解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"

输出：6

解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"

输出：3

解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

s 仅由小写英文字母组成

序列 DP

为了方便，我们令 s 下标从开始，定义为考虑前个字符，且结尾字符为的不同子序列的个数，其中的范围为代指小写字符 a-z。

我们有显而易见的初始化条件，最终答案为。

不失一般性考虑该如何转移，根据是否为进行分情况讨论：

: 由于状态定义限定了结尾字符必须是，因而必然不会用到，此时有：

: 此时可作为结尾元素，同时由于我们统计的是「不同」的子序列个数，因而「以结尾的子序列方案数」与「以结尾的子序列方案数」完全等价。对于以作为子序列结尾字符的方案数，容易想到其方案数等于「单独作为子序列」+「拼接在其余子序列后面形成新子序列」，即有：

Java 代码：

class Solution {
    int MOD = (int)1e9+7;
    public int distinctSubseqII(String s) {
        int n = s.length(), ans = 0;
        int[][] f = new int[n + 1][26];
        for (int i = 1; i <= n; i++) {
            int c = s.charAt(i - 1) - 'a';
            for (int j = 0; j < 26; j++) {
                if (c != j) {
                    f[i][j] = f[i - 1][j];
                } else {
                    int cur = 1;
                    for (int k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD;
                    f[i][j] = cur;
                }
            }
        }
        for (int i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD;
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.length(), MOD = 1e9 + 7;
        vector<vector<int>> f(n + 1, vector<int>(26, 0));
        for (int i = 1; i <= n; ++i) {
            int c = s[i - 1] - 'a';
            for (int j = 0; j < 26; ++j) {
                if (c != j) {
                    f[i][j] = f[i - 1][j];
                } else {
                    int cur = 1;
                    for (int k = 0; k < 26; ++k) cur = (cur + f[i - 1][k]) % MOD;
                    f[i][j] = cur;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; ++i) ans = (ans + f[n][i]) % MOD;
        return ans;
    }
};

Python 代码：

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n, MOD = len(s), 1e9+7
        f = [[0] * 26 for _ in range(n + 1)]
        for i in range(1, n + 1):
            c = ord(s[i - 1]) - ord('a')
            for j in range(26):
                f[i][j] = f[i - 1][j] if c != j else (1 + sum(f[i - 1])) % MOD
        return int(sum(f[n]) % MOD)

TypeScript 代码：

function distinctSubseqII(s: string): number {
    const MOD = 1e9+7
    let n = s.length, ans = 0
    const f = new Array<Array<number>>(n + 1)
    for (let i = 0; i <= n; i++) f[i] = new Array<number>(26).fill(0)
    for (let i = 1; i <= n; i++) {
        const c = s.charCodeAt(i - 1) - 'a'.charCodeAt(0)
        for (let j = 0; j < 26; j++) {
            if (c != j) {
                f[i][j] = f[i - 1][j]
            } else {
                let cur = 1
                for (let k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD
                f[i][j] = cur
            }
        }
    }
    for (let i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD
    return ans
}

时间复杂度：，其中为字符集大小
空间复杂度：

转移优化

根据转移的依赖关系，实现上，我们并不需要真正记录每一个，而可以直接记录一个总的不同子序列方案数 ans。

这可以避免每次计算新状态时，都累加前一个的值，有效减低时空复杂度。

Java 代码：

class Solution {
    int MOD = (int)1e9+7;
    public int distinctSubseqII(String s) {
        int n = s.length(), ans = 0;
        int[] f = new int[26];
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a', prev = f[c];
            f[c] = (ans + 1) % MOD;
            ans = (ans + f[c]) % MOD;
            ans = (ans - prev + MOD) % MOD;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.length(), ans = 0, MOD = 1e9 + 7;
        vector<int> f(26, 0);
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a', prev = f[c];
            f[c] = (ans + 1) % MOD;
            ans = (ans + f[c]) % MOD;
            ans = (ans - prev + MOD) % MOD;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n, MOD, ans = len(s), 1e9+7, 0
        f = [0] * 26
        for i in range(n):
            c = ord(s[i]) - ord('a')
            prev = f[c]
            f[c] = (ans + 1) % MOD
            ans = (ans + f[c] - prev) % MOD            
        return int(ans)

TypeScript 代码：

function distinctSubseqII(s: string): number {
    const MOD = 1e9+7
    let n = s.length, ans = 0
    const f = new Array<number>(26).fill(0)
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - 'a'.charCodeAt(0), prev = f[c]
        f[c] = (ans + 1) % MOD
        ans = (ans + f[c]) % MOD
        ans = (ans - prev + MOD) % MOD
    }
    return ans
}