2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少； I 意味着增加。 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm
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 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);
}
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 i
int 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;
}
公众号：福大大架构师每日一题