903. Valid Permutations for DI Sequence

LeetCode hard оригинал: C# #array #csharp #dynamic-programming #hard #leetcode #string

LeetCode Static

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"

Output: 5

C# решение

сопоставлено/оригинал

public class Solution {
    public int NumPermsDISequence(string s) {
        int MOD = 1_000_000_007;
        int n = s.Length;
        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[n + 1];
        }
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[i - 1] == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumPermsDISequence(string s) {
        int MOD = 1_000_000_007;
        int n = s.size();
        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[n + 1];
        }
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[i - 1] == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int numPermsDISequence(String s) {
        int MOD = 1_000_000_007;
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i - 1) == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
}

JavaScript решение

сопоставлено/оригинал

var numPermsDISequence = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (s[i - 1] === 'D') {
                dp[i][j] = dp[i - 1].slice(j, i).reduce((sum, x) => (sum + x) % MOD, 0);
            } else {
                dp[i][j] = dp[i - 1].slice(0, j).reduce((sum, x) => (sum + x) % MOD, 0);
            }
        }
    }

    return dp[n].reduce((sum, x) => (sum + x) % MOD, 0);
};

Go решение

сопоставлено/оригинал

package main

func numPermsDISequence(s string) int {
    const MOD = 1_000_000_007
    n := len(s)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    dp[0][0] = 1

    for i := 1; i <= n; i++ {
        for j := 0; j <= i; j++ {
            if s[i-1] == 'D' {
                for k := j; k < i; k++ {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
                }
            } else {
                for k := 0; k < j; k++ {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
                }
            }
        }
    }

    result := 0
    for j := 0; j <= n; j++ {
        result = (result + dp[n][j]) % MOD
    }

    return result
}

Algorithm

Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.