2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是:
D 意味着减少；
I 意味着增加。
有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：
如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。
返回 有效排列 perm 的数量 。因为答案可能很大，所以请返回你的答案对 10^9 + 7 取余。
输入：s = "DID"。
输出：5。
答案 2023-05-22：
算法 1：暴力枚举
1.定义递归函数 ways(s []byte, i int, less int, n int) int，其中 s 为要判断的字符串，i 表示当前要填入的位置，less 记录上一个数的大小信息，n 表示总共有 n + 1 个数字需要填。
2.如果 i 等于 n，则返回 1，表示已经填完了。
3.如果 i 等于 0 或 s[i-1] 等于 'D'，则循环从 0 到 less - 1 枚举下一个数 nextLess，并将结果加到 ans 上。每次递归调用时将 i 增加 1，并更新 less 的值为 nextLess。最后返回 ans。
4.否则 s[i-1] 等于 'I'，则循环从 less 到 n-i 枚举下一个数 nextLess，并将结果加到 ans 上。每次递归调用时将 i 增加 1，并更新 less 的值为 nextLess。最后返回 ans。
时间复杂度：O(n!)，其中 n 为数字序列的长度。
空间复杂度：O(n)，递归过程中需要 O(n) 的栈空间。
算法 2：动态规划
1.定义二维数组 dp，其中 dp[i][j] 表示在第 i 个位置填入数字 j 的情况下满足条件的排列的数量。
2.初始化 dp[n][less] 为 1，表示在最后一个位置填入 less 的数量只有一种。
3.从倒数第二个位置开始往前遍历，根据当前位置 s[i-1] 的值，分别枚举下一个数字的大小。如果 s[i-1] 等于 'D'，则循环从 0 到 less - 1 枚举下一个数字的大小，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。
4.如果 s[i-1] 等于 'I'，则循环从 less 到 n-i 枚举下一个数字的大小，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。
5.最终答案为 dp[0][n]。
时间复杂度：O(n^2)，需要填充一个二维数组，数组大小为 n * (n+1)。
空间复杂度：O(n^2)，需要使用一个二维数组来存储状态。
算法 3：动态规划 + 优化
1.定义二维数组 dp，其中 dp[i][j] 表示在第 i 个位置填入数字 j 的情况下满足条件的排列的数量。
2.初始化 dp[n][less] 为 1，表示在最后一个位置填入 less 的数量只有一种。
3.从倒数第二个位置开始往前遍历，根据当前位置 s[i-1] 的值，分别枚举下一个数字的大小。如果 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.在循环中记录当前已经累计的和 sum，然后 dp[i][less] 的值更新为 sum，同时需要考虑取模的问题。具体来说，如果当前的 sum 大于 mod，则减去一个 mod；如果当前的 sum 小于 0，则加上一个 mod。
6.最终答案为 dp[0][n]。
时间复杂度：O(n)，只需填充一个一维数组即可。
空间复杂度：O(n)，只需使用一个一维数组来存储状态。
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 : 填的数字的位// 3 5 2// 0 1 2// I D// less :// 之前填的数字X，后面剩下的数字中有几个比X小！// X// i-1 ifn 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);}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>
int ways1(char* s, int i, int less, int n);int numPermsDISequence1(char* s);int numPermsDISequence2(char* str);int numPermsDISequence3(char* str);
int main() { char s[] = "DID"; printf("%d\n", numPermsDISequence1(s)); printf("%d\n", numPermsDISequence2(s)); printf("%d\n", numPermsDISequence3(s)); return 0;}
int numPermsDISequence1(char* s) { return ways1(s, 0, strlen(s) + 1, strlen(s) + 1);}
int ways1(char* s, int i, int less, int n) { int ans = 0; if (i == n) { ans = 1; } else if (i == 0 || *(s + i - 1) == 'D') { for (int nextLess = 0; nextLess < less; nextLess++) { ans += ways1(s, i + 1, nextLess, n); } } else { for (int nextLess = less; nextLess < n - i; nextLess++) { ans += ways1(s, i + 1, nextLess, n); } } return ans;}
int numPermsDISequence2(char* s) { int mod = 1000000007; int n = strlen(s) + 1; int** dp = (int**)malloc((n + 1) * sizeof(int*)); for (int i = 0; i <= n; i++) { dp[i] = (int*)malloc((n + 1) * sizeof(int)); } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; } }
for (int less = 0; less <= n; less++) { dp[n][less] = 1; } for (int i = n - 1; i >= 0; i--) { for (int less = 0; less <= n; less++) { if (i == 0 || s[i - 1] == 'D') { for (int nextLess = 0; nextLess < less; nextLess++) { dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod; } } else { for (int nextLess = less; nextLess < n - i; nextLess++) { dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod; } } } } int res = dp[0][n]; for (int i = 0; i <= n; i++) { free(dp[i]); } free(dp); return res;}
int numPermsDISequence3(char* s) { int mod = 1000000007; int n = strlen(s) + 1; int** dp = (int**)malloc((n + 1) * sizeof(int*)); for (int i = 0; i <= n; i++) { dp[i] = (int*)malloc((n + 1) * sizeof(int)); }
for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; } }
for (int less = 0; less <= n; less++) { dp[n][less] = 1; } for (int i = n - 1; i >= 0; i--) { if (i == 0 || s[i - 1] == 'D') { for (int less = 0; less <= n; less++) { dp[i][less] = less - 1 >= 0 ? ((dp[i][less - 1] + dp[i + 1][less - 1]) % mod) : 0; } } else { // s[i-1] = 'I' dp[i][n - i - 1] = dp[i + 1][n - i - 1]; for (int less = n - i - 2; less >= 0; less--) { dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod; } } } int res = dp[0][n]; for (int i = 0; i <= n; i++) { free(dp[i]); } free(dp); return res;}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <cstring>
using namespace std;
int ways1(vector<char>& s, int i, int less, int n);int numPermsDISequence1(string s);int numPermsDISequence2(string s);int numPermsDISequence3(string s);
// i : 填的数字的位// 3 5 2// 0 1 2// I D// less :之前填的数字X，后面剩下的数字中有几个比X小！// X// i-1 iint ways1(vector<char>& s, int i, int less, int n) { int ans = 0; if (i == n) { ans = 1; } else if (i == 0 || s[i - 1] == 'D') { for (int nextLess = 0; nextLess < less; nextLess++) { ans += ways1(s, i + 1, nextLess, n); } } else { // s[i-1] = 'I' for (int nextLess = less; nextLess < n - i; nextLess++) { ans += ways1(s, i + 1, nextLess, n); } } return ans;}
int numPermsDISequence1(string s) { vector<char> str(s.begin(), s.end()); str.push_back('I'); return ways1(str, 0, s.length() + 1, s.length() + 1);}
int numPermsDISequence2(string s) { int mod = 1000000007; vector<char> str(s.begin(), s.end()); str.push_back('I'); int n = str.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 1)); for (int less = 0; less <= n; less++) { dp[n][less] = 1; } for (int i = n - 1; i >= 0; i--) { for (int less = 0; less <= n; less++) { if (i == 0 || str[i - 1] == 'D') { for (int nextLess = 0; nextLess < less; nextLess++) { dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod; } } else { for (int nextLess = less; nextLess < n - i; nextLess++) { dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod; } } } } return dp[0][n];}
int numPermsDISequence3(string s) { int mod = 1000000007; vector<char> str(s.begin(), s.end()); str.push_back('I'); int n = str.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 1)); for (int less = 0; less <= n; less++) { dp[n][less] = 1; } for (int i = n - 1; i >= 0; i--) { if (i == 0 || str[i - 1] == 'D') { for (int less = 0; less <= n; less++) { dp[i][less] = less - 1 >= 0 ? ((dp[i][less - 1] + dp[i + 1][less - 1]) % mod) : 0; } } else { // str[i-1] = 'I' dp[i][n - i - 1] = dp[i + 1][n - i - 1]; for (int less = n - i - 2; less >= 0; less--) { dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod; } } } return dp[0][n];}
int main() { string s = "DID"; cout << numPermsDISequence1(s) << endl; // expect 5 cout << numPermsDISequence2(s) << endl; // expect 5 cout << numPermsDISequence3(s) << endl; // expect 5 return 0;}
复制代码
![2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少； I 意味着增加。 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm_Go_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论