2023-05-22：給定一個長度為 n 的字符串 s ，其中 s[i] 是:

D 意味著減少；

I 意味著增加。

有效排列 是對有 n + 1 個在 [0, n] 范圍內(nèi)的整數(shù)的一個排列 perm ，使得對所有的 i：

如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；

如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的數(shù)量 。因為答案可能很大，所以請返回你的答案對 10^9 + 7 取余。

輸入：s = "DID"。

輸出：5。

答案2023-05-22：

算法1：暴力枚舉

1.定義遞歸函數(shù) ways(s []byte, i int, less int, n int) int，其中 s 為要判斷的字符串，i 表示當前要填入的位置，less 記錄上一個數(shù)的大小信息，n 表示總共有 n + 1 個數(shù)字需要填。

2.如果 i 等于 n，則返回 1，表示已經(jīng)填完了。

3.如果 i 等于 0 或 s[i-1] 等于 'D'，則循環(huán)從 0 到 less - 1 枚舉下一個數(shù) nextLess，并將結(jié)果加到 ans 上。每次遞歸調(diào)用時將 i 增加 1，并更新 less 的值為 nextLess。最后返回 ans。

4.否則 s[i-1] 等于 'I'，則循環(huán)從 less 到 n-i 枚舉下一個數(shù) nextLess，并將結(jié)果加到 ans 上。每次遞歸調(diào)用時將 i 增加 1，并更新 less 的值為 nextLess。最后返回 ans。

時間復(fù)雜度：O(n!)，其中 n 為數(shù)字序列的長度。

空間復(fù)雜度：O(n)，遞歸過程中需要 O(n) 的?？臻g。

算法2：動態(tài)規(guī)劃

1.定義二維數(shù)組 dp，其中 dp[i][j] 表示在第 i 個位置填入數(shù)字 j 的情況下滿足條件的排列的數(shù)量。

2.初始化 dp[n][less] 為 1，表示在最后一個位置填入 less 的數(shù)量只有一種。

3.從倒數(shù)第二個位置開始往前遍歷，根據(jù)當前位置 s[i-1] 的值，分別枚舉下一個數(shù)字的大小。如果 s[i-1] 等于 'D'，則循環(huán)從 0 到 less - 1 枚舉下一個數(shù)字的大小，將 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

4.如果 s[i-1] 等于 'I'，則循環(huán)從 less 到 n-i 枚舉下一個數(shù)字的大小，將 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

5.最終答案為 dp[0][n]。

時間復(fù)雜度：O(n^2)，需要填充一個二維數(shù)組，數(shù)組大小為 n * (n+1)。

空間復(fù)雜度：O(n^2)，需要使用一個二維數(shù)組來存儲狀態(tài)。

算法3：動態(tài)規(guī)劃 + 優(yōu)化

1.定義二維數(shù)組 dp，其中 dp[i][j] 表示在第 i 個位置填入數(shù)字 j 的情況下滿足條件的排列的數(shù)量。

2.初始化 dp[n][less] 為 1，表示在最后一個位置填入 less 的數(shù)量只有一種。

3.從倒數(shù)第二個位置開始往前遍歷，根據(jù)當前位置 s[i-1] 的值，分別枚舉下一個數(shù)字的大小。如果 s[i-1] 等于 'D'，則從 0 到 less 枚舉 nextLess，將 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

4.如果 s[i-1] 等于 'I'，則從 n-i 到 less 枚舉 nextLess，將 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

5.在循環(huán)中記錄當前已經(jīng)累計的和 sum，然后 dp[i][less] 的值更新為 sum，同時需要考慮取模的問題。具體來說，如果當前的 sum 大于 mod，則減去一個 mod；如果當前的 sum 小于 0，則加上一個 mod。

6.最終答案為 dp[0][n]。

時間復(fù)雜度：O(n)，只需填充一個一維數(shù)組即可。

空間復(fù)雜度：O(n)，只需使用一個一維數(shù)組來存儲狀態(tài)。

go完整代碼如下：

package?main

import?"fmt"

func?numPermsDISequence1(s?string)?int?{
????n?:=?len(s)?+?1
????return?ways1([]byte(s),?0,?n,?n)
}

func?ways1(s?[]byte,?i?int,?less?int,?n?int)?int?{
????if?i?==?n?{
????????return?1
????}?else?if?i?==?0?||?s[i-1]?==?'D'?{
????????ans?:=?0
????????for?nextLess?:=?0;?nextLess?<?less;?nextLess++?{
????????????ans?+=?ways1(s,?i+1,?nextLess,?n)
????????}
????????return?ans
????}?else?{?//?s[i-1]?=?'I'
????????ans?:=?0
????????for?nextLess?:=?less;?nextLess?<?n-i;?nextLess++?{
????????????ans?+=?ways1(s,?i+1,?nextLess,?n)
????????}
????????return?ans
????}
}

func?numPermsDISequence2(s?string)?int?{
????mod?:=?1000000007
????n?:=?len(s)?+?1
????dp?:=?make([][]int,?n+1)
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int,?n+1)
????}
????for?less?:=?0;?less?<=?n;?less++?{
????????dp[n][less]?=?1
????}
????for?i?:=?n?-?1;?i?>=?0;?i--?{
????????for?less?:=?0;?less?<=?n;?less++?{
????????????if?i?==?0?||?s[i-1]?==?'D'?{
????????????????for?nextLess?:=?0;?nextLess?<?less;?nextLess++?{
????????????????????dp[i][less]?=?(dp[i][less]?+?dp[i+1][nextLess])?%?mod
????????????????}
????????????}?else?{
????????????????for?nextLess?:=?less;?nextLess?<?n-i;?nextLess++?{
????????????????????dp[i][less]?=?(dp[i][less]?+?dp[i+1][nextLess])?%?mod
????????????????}
????????????}
????????}
????}
????return?dp[0][n]
}

func?numPermsDISequence3(s?string)?int?{
????mod?:=?1000000007
????n?:=?len(s)?+?1
????dp?:=?make([][]int,?n+1)
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int,?n+1)
????}
????for?less?:=?0;?less?<=?n;?less++?{
????????dp[n][less]?=?1
????}
????for?i?:=?n?-?1;?i?>=?0;?i--?{
????????if?i?==?0?||?s[i-1]?==?'D'?{
????????????for?less?:=?0;?less?<=?n;?less++?{
????????????????if?less?>?0?{
????????????????????dp[i][less]?=?(dp[i][less-1]?+?dp[i+1][less-1])?%?mod
????????????????}?else?{
????????????????????dp[i][less]?=?0
????????????????}
????????????}
????????}?else?{?//?s[i-1]?=?'I'
????????????dp[i][n-i-1]?=?dp[i+1][n-i-1]
????????????for?less?:=?n?-?i?-?2;?less?>=?0;?less--?{
????????????????dp[i][less]?=?(dp[i][less+1]?+?dp[i+1][less])?%?mod
????????????}
????????}
????}
????return?dp[0][n]
}

func?main()?{
????s?:=?"DID"
????res?:=?numPermsDISequence1(s)
????fmt.Println(res)

????res?=?numPermsDISequence2(s)
????fmt.Println(res)

????res?=?numPermsDISequence3(s)
????fmt.Println(res)
}


rust語言完整代碼如下：

fn?num_perms_di_sequence1(s:?String)?->?i32?{
????let?s?=?s.as_bytes();
????let?n?=?s.len()?+?1;
????ways1(s,?0,?n,?n)
}

//?i?:?填的數(shù)字的位
//?3?5?2
//?0?1?2
//??I?D
//?less?:
//?之前填的數(shù)字X，后面剩下的數(shù)字中有幾個比X小！
//?????????X
//????????i-1?i
fn?ways1(s:?&[u8],?i:?usize,?less:?usize,?n:?usize)?->?i32?{
????if?i?==?n?{
????????return?1;
????}?else?if?i?==?0?||?s[i?-?1]?==?b'D'?{
????????(0..less)
????????????.map(|next_less|?ways1(s,?i?+?1,?next_less,?n))
????????????.sum()
????}?else?{
????????//?s[i-1]?=?b'I'
????????((less?as?isize)..((n?-?i)?as?isize))
????????????.map(|next_less|?ways1(s,?i?+?1,?next_less?as?usize,?n))
????????????.sum()
????}
}

fn?num_perms_di_sequence2(s:?String)?->?i32?{
????let?s?=?s.as_bytes();
????let?n?=?s.len()?+?1;
????let?mod_num?=?1000000007;

????let?mut?dp?=?vec![vec![0;?n?+?1];?n?+?1];
????for?less?in?0..=n?{
????????dp[n][less]?=?1;
????}

????let?mut?i?=?n?as?i32?-?1;
????while?i?>=?0?{
????????for?less?in?0..=n?{
????????????if?i?==?0?||?s[(i?-?1)?as?usize]?==?b'D'?{
????????????????for?next_less?in?0..less?{
????????????????????dp[i?as?usize][less]?=
????????????????????????(dp[i?as?usize][less]?+?dp[i?as?usize?+?1][next_less])?%?mod_num;
????????????????}
????????????}?else?{
????????????????//?s[i-1]?=?b'I'
????????????????for?next_less?in?less..n?-?i?as?usize?{
????????????????????dp[i?as?usize][less]?=
????????????????????????(dp[i?as?usize][less]?+?dp[i?as?usize?+?1][next_less])?%?mod_num;
????????????????}
????????????}
????????}
????????i?-=?1;
????}
????dp[0][n]
}

fn?num_perms_di_sequence3(s:?String)?->?i32?{
????let?s?=?s.as_bytes();
????let?n?=?s.len()?+?1;
????let?mod_num?=?1000000007;

????let?mut?dp?=?vec![vec![0;?n?+?1];?n?+?1];
????for?less?in?0..=n?{
????????dp[n][less]?=?1;
????}

????let?mut?i?=?n?as?i32?-?1;
????while?i?>=?0?{
????????if?i?==?0?||?s[i?as?usize?-?1]?==?b'D'?{
????????????for?less?in?0..=n?{
????????????????dp[i?as?usize][less]?=?if?less?>?0?{
????????????????????(dp[i?as?usize][less?-?1]?+?dp[i?as?usize?+?1][less?-?1])?%?mod_num
????????????????}?else?{
????????????????????0
????????????????}
????????????}
????????}?else?{
????????????//?s[i-1]?=?b'I'
????????????dp[i?as?usize][n?-?i?as?usize?-?1]?=?dp[i?as?usize?+?1][n?-?i?as?usize?-?1];
????????????let?mut?less?=?n?as?i32?-?i?-?2;
????????????while?less?>=?0?{
????????????????dp[i?as?usize][less?as?usize]?=?(dp[i?as?usize][less?as?usize?+?1]
????????????????????+?dp[i?as?usize?+?1][less?as?usize])
????????????????????%?mod_num;
????????????????less?-=?1;
????????????}
????????}
????????i?-=?1;
????}
????dp[0][n]
}

fn?main()?{
????let?s?=?String::from("DID");
????let?res?=?num_perms_di_sequence1(s);
????println!("{}",?res);

????let?s?=?String::from("DID");
????let?res?=?num_perms_di_sequence2(s);
????println!("{}",?res);

????let?s?=?String::from("DID");
????let?res?=?num_perms_di_sequence3(s);
????println!("{}",?res);
}