Algorithms: Dynamic Programming

int rod_cutting(const std::vector<int>& prices, int n) {
    alg_require(prices.size() <= 1000000);
    alg_require(((n >= 0) && (n <= 1000000)));
    std::vector<int> dp(alg_size(alg_add(n, 1)), 0);
    int length = 1;
    int cut = 0;
    while ((length <= n)) {
        cut = 1;
        while ((cut <= length)) {
            dp[length] = alg_max(dp[length], alg_add(prices[alg_sub(cut, 1)], dp[alg_sub(length, cut)]));
            cut = alg_add(cut, 1);
        }

function fibonacci(int $n): int {
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((($n >= 0) && ($n <= 45)));
    $a = 0;
    $b = 1;
    $next_value = 0;
    $i = 0;
    while (($i < $n)) {
        $next_value = alg_add($a, $b);
        $a = $b;
        $b = $next_value;
        $i = alg_add($i, 1);

def rod_cutting(prices: list[int], n: int) -> int:
    alg_require(isinstance(prices, (list, tuple)) and len(prices) <= 1000000)
    alg_require(type(n) is int and -2147483648 <= n <= 2147483647)
    alg_require(n >= 0 and n <= 1000000)
    dp: list[int] = [0] * alg_size(n + 1)
    length: int = 1
    cut: int = 0
    while length <= n:
        cut = 1
        while cut <= length:
            dp[length] = max(dp[length], prices[cut - 1] + dp[length - cut])
            cut += 1

function rod_cutting(prices, n) {
    alg_require(prices instanceof Int32Array);
    alg_require(Number.isInteger(n) && n >= -2147483648 && n <= 2147483647);
    alg_require(((n >= 0) && (n <= 1000000)));
    let dp = new Int32Array(alg_size(alg_add(n, 1)));
    let length = 1;
    let cut = 0;
    while ((length <= n)) {
        cut = 1;
        while ((cut <= length)) {
            dp[length] = Math.max(dp[length], alg_add(prices[alg_sub(cut, 1)], dp[alg_sub(length, cut)]));
            cut = alg_add(cut, 1);

    static int rod_cutting(int[] prices, int n) {
        java.util.Objects.requireNonNull(prices, "prices");
        alg_require(((n >= 0) && (n <= 1000000)));
        int[] dp = new int[alg_size(Math.addExact(n, 1))];
        int length = 1;
        int cut = 0;
        while ((length <= n)) {
            cut = 1;
            while ((cut <= length)) {
                dp[length] = Math.max(dp[length], Math.addExact(prices[Math.subtractExact(cut, 1)], dp[Math.subtractExact(length, cut)]));
                cut = Math.addExact(cut, 1);
            }