大膽預測：計算機將要回暖

中概財報集體亮眼

雖然最近幾天恒指（港股）稍有回落，但年線仍有 9% 的上漲。

過去三年，恒指分別下跌 14.08%、15.46% 和 13.82%。

而在近期，國內各大互聯網都公布了財報，別看各個大廠的作妖不斷，但這次似乎真的有點「否極泰來」的意思了：

騰訊凈利潤 418.89 億，同比增長 62.12%
拼多多凈利潤 279.98 億，同比增長 245.61%
阿里凈利潤 244.18 億，同比增長 -10.80%
網易凈利潤 76.34 億，同比增長 13.02%
京東凈利潤 71.30 億，同比增長 13.88%
小米凈利潤 64.9 億，同比增長 100%
百度凈利潤 54.48 億，同比增長 -6.47%
攜程凈利潤 43.12 億，同比增長 27.76%
快手凈利潤 41.19 億，同比增長 571.82%

現在提到「互聯網」和「計算機」，大多數聲音還都是「裁員」、「人擠人」和「找不到工作」，但財務數據才是真實的，而且從「金融資本市場」到「勞動力市場」往往有 1~2 年的滯后性。

現在往回看，其實國內互聯網的轉向是從 2021 年年初就開始的，但 2021 年的招聘市場，大家都知道的。流行語是「打得火熱」、「跳槽薪資翻倍」和「應屆生實習工資水漲船高，直接倒掛老員工」，所謂的「裁員」和「寒氣」是從 2022 下半年才開始大面積盛行的。

所以根據現在掌握的信息來看，我可以大膽給出結論：計算機看不到希望的長夜已經過去，回暖是大概率的事情。

我給大家的建議，抓緊學習，厚積薄發，好日子快回來了。

如果因為現在的行情決定「轉行」或者「放棄轉碼」，大概率不會變得更好，而且可能還會成為倒在黎明的那一批。

...

回歸主題。

來一道和「字節跳動」相關的題目（不要問我為啥最近都是字節跳動，宇宙廠的投稿太多了 🤣

題目描述

平臺：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 下標從 1 開始，定義為考慮前 i 個字符，且結尾字符為 j 的不同子序列的個數，其中 j 的范圍為代指小寫字符 a-z。

我們有顯而易見的初始化條件，最終答案為。

不失一般性考慮該如何轉移，根據是否為 j 進行分情況討論：

: 由于狀態定義限定了結尾字符必須是，因而必然不會用到，此時有：

: 此時可作為結尾元素，同時由于我們統計的是「不同」的子序列個數，因而「以結尾的子序列方案數」與「以結尾的子序列方案數」完全等價。對于以作為子序列結尾字符的方案數，容易想到其方案數等于「單獨作為子序列」+「拼接在其余子序列后面形成新子序列」，即有：

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
}