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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接