当前位置：首页 > PHP

动态规划实现 php

2026-02-15 23:19:31PHP

动态规划简介

动态规划（Dynamic Programming, DP）是一种通过将问题分解为子问题并存储子问题解来优化计算的方法，适用于具有重叠子问题和最优子结构性质的问题。

PHP 实现动态规划的步骤

定义状态
明确问题的状态表示，通常用数组或变量存储子问题的解。例如，斐波那契数列中，dp[i] 表示第 i 项的值。

状态转移方程
根据问题逻辑建立状态之间的关系。斐波那契数列的状态转移方程为：
$$ dp[i] = dp[i-1] + dp[i-2] $$

初始化
设置初始状态的值。斐波那契数列中，dp[0] = 0 和 dp[1] = 1。

计算顺序
通常从最小子问题开始迭代计算，逐步填充状态表。

示例：斐波那契数列

function fibonacci($n) {
    if ($n <= 1) return $n;
    $dp = array();
    $dp[0] = 0;
    $dp[1] = 1;
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}
echo fibonacci(10); // 输出 55

示例：背包问题

0-1 背包问题的动态规划解法：

function knapSack($W, $weights, $values, $n) {
    $dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));
    for ($i = 1; $i <= $n; $i++) {
        for ($w = 1; $w <= $W; $w++) {
            if ($weights[$i - 1] <= $w) {
                $dp[$i][$w] = max(
                    $values[$i - 1] + $dp[$i - 1][$w - $weights[$i - 1]],
                    $dp[$i - 1][$w]
                );
            } else {
                $dp[$i][$w] = $dp[$i - 1][$w];
            }
        }
    }
    return $dp[$n][$W];
}

$values = [60, 100, 120];
$weights = [10, 20, 30];
$W = 50;
$n = count($values);
echo knapSack($W, $weights, $values, $n); // 输出 220

优化空间复杂度

某些问题可以通过滚动数组或一维数组优化空间。例如斐波那契数列的优化实现：

动态规划实现 php

function fibonacciOptimized($n) {
    if ($n <= 1) return $n;
    $prev1 = 1;
    $prev2 = 0;
    for ($i = 2; $i <= $n; $i++) {
        $current = $prev1 + $prev2;
        $prev2 = $prev1;
        $prev1 = $current;
    }
    return $prev1;
}