騰訊

昨天騰訊公布了 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
}

• 時間復雜度：
• 空間復雜度：

最后

巨劃算的 LeetCode 會員優惠通道目前仍可用 ~

使用福利優惠通道 leetcode.cn/premium/?promoChannel=acoier，年度會員 有效期額外增加兩個月，季度會員 有效期額外增加兩周，更有超大額專屬 🧧 和實物 🎁 福利每月發放。

我是宮水三葉，每天都會分享算法知識，并和大家聊聊近期的所見所聞。

歡迎關注，明天見。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的 合集新基地 🎉🎉