Algorithms: Dynamic Programming

    static int unbounded_knapsack(ReadOnlySpan<int> weights, ReadOnlySpan<int> values, int capacity) {
        checked {
            int n = weights.Length;
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require((weights.Length == n));
            alg_require((values.Length == n));
            alg_require(((capacity >= 0) && (capacity <= 1000000)));
            for (int alg_i = 0; alg_i < weights.Length; alg_i++) {
                int alg_value = weights[alg_i];
                alg_require((alg_value > 0));
            }
            for (int alg_i = 0; alg_i < values.Length; alg_i++) {

function unbounded_knapsack(array $weights, array $values, int $capacity): int {
    alg_require(array_is_list($weights));
    alg_require(array_is_list($values));
    $n = count($weights);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($weights) == $n));
    alg_require((count($values) == $n));
    alg_require((($capacity >= 0) && ($capacity <= 1000000)));
    for ($alg_i = 0; $alg_i < count($weights); $alg_i++) {
        $alg_value = $weights[$alg_i];
        alg_require(($alg_value > 0));
    }

    static int regex_match(int[] text, int[] pattern) {
        java.util.Objects.requireNonNull(text, "text");
        java.util.Objects.requireNonNull(pattern, "pattern");
        int n = text.length;
        int m = pattern.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require(((m >= 0) && (m <= 1000000)));
        alg_require((pattern.length == m));
        alg_require((text.length == n));
        for (int alg_i = 0; alg_i < m; alg_i++) {
            alg_require((pattern[alg_i] >= Math.negateExact(2)));
            alg_require(((pattern[alg_i] != Math.negateExact(2)) || ((alg_i > 0) && (pattern[Math.subtractExact(alg_i, 1)] != Math.negateExact(2)))));

function regex_match(text, pattern) {
    alg_require(text instanceof Int32Array);
    alg_require(pattern instanceof Int32Array);
    let n = text.length;
    let m = pattern.length;
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((m >= 0) && (m <= 1000000)));
    alg_require((pattern.length == m));
    alg_require((text.length == n));
    for (let alg_i = 0; alg_i < m; alg_i++) {
        alg_require((pattern[alg_i] >= alg_sub(0, 2)));
        alg_require(((pattern[alg_i] != alg_sub(0, 2)) || ((alg_i > 0) && (pattern[alg_sub(alg_i, 1)] != alg_sub(0, 2)))));

def regex_match(text: list[int], pattern: list[int]) -> int:
    alg_require(isinstance(text, (list, tuple)) and len(text) <= 1000000)
    alg_require(isinstance(pattern, (list, tuple)) and len(pattern) <= 1000000)
    n: int = len(text)
    m: int = len(pattern)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(m >= 0 and m <= 1000000)
    alg_require(len(pattern) == m)
    alg_require(len(text) == n)
    for i, value in enumerate(pattern):
        alg_require(value >= -2 and (value != -2 or (i > 0 and pattern[i - 1] != -2)))
    dp: list[int] = [0] * alg_size((n + 1) * (m + 1))