Algorithms: Dynamic Programming Tutorials and Code Examples - Page 12

Fast Doubling Fibonacci in PHP

Fast doubling computes Fibonacci numbers using identities for doubling an index, reducing the number of recurrence steps logarithmically..

php

function fast_fibonacci(int $n): int {
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((($n >= 0) && ($n <= 45)));
    $a = 0;
    $b = 1;
    $c = 0;
    $d = 0;
    $bit = 1;
    while (($bit <= intdiv($n, 2))) {
        $bit = alg_mul($bit, 2);
    }
    while (($bit > 0)) {

Nov 15, 2026 PHP

Algorithms: Dynamic Programming

0-1 Knapsack in C++

Knapsack chooses items with maximum total value under a weight limit, using each item at most once.

cpp

int knapsack(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    alg_require(weights.size() <= 1000000);
    alg_require(values.size() <= 1000000);
    int n = (int)weights.size();
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((int)weights.size() == n));
    alg_require(((int)values.size() == n));
    alg_require(((capacity >= 0) && (capacity <= 1000000)));
    for (int alg_i = 0; alg_i < (int)weights.size(); alg_i++) {
        int alg_value = weights[alg_i];
        alg_require((alg_value > 0));
    }

Nov 15, 2026 C++

Algorithms: Dynamic Programming

Levenshtein Edit Distance in C

Edit distance counts the minimum unit-cost insertions, deletions, and substitutions needed to turn one token sequence into another..

c

int edit_distance(const int *a, size_t a_length, const int *b, size_t b_length) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *dp = NULL;
    if (a_length > 1000000 || (a_length && !a)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (b_length > 1000000 || (b_length && !b)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)a_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int m = (int)b_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }

Nov 15, 2026 C

Algorithms: Dynamic Programming

0-1 Knapsack in C#

Knapsack chooses items with maximum total value under a weight limit, using each item at most once.

csharp

    static int 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++) {

Nov 15, 2026 csharp

Algorithms: Dynamic Programming

Minimum Coin Change in PHP

Minimum coin change finds the fewest coins needed to make an exact amount when each denomination can be reused.

php

function minimum_coins(array $coins, int $amount): int {
    alg_require(array_is_list($coins));
    $m = count($coins);
    alg_require((($m >= 0) && ($m <= 1000000)));
    alg_require((count($coins) == $m));
    alg_require((($amount >= 0) && ($amount <= 1000000)));
    for ($alg_i = 0; $alg_i < count($coins); $alg_i++) {
        $alg_value = $coins[$alg_i];
        alg_require(($alg_value > 0));
    }
    $dp = array_fill(0, alg_size(alg_add($amount, 1)), 0);
    $x = 1;

Nov 15, 2026 PHP