2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少； I 意味着增加。 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm

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

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

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

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