什么是动态规划
动态规划是一种将复杂问题拆分成多个子问题，通过保存子问题的解来避免重复计算，最终得到原问题最优解的算法思想。在PHP算法面试中，动态规划相关的题目通常考察求职者对问题拆解、状态定义、转移逻辑设计的能力，是区分基础算法水平和进阶能力的重要考点。
PHP动态规划解题的核心步骤
在PHP中解答动态规划类面试题，通常遵循以下固定步骤：
- 定义状态：明确dp数组每个元素代表的含义，比如dp[i]表示前i个元素的最优解
- 设置初始条件：确定dp数组的初始值，避免后续计算出现越界或逻辑错误
- 推导状态转移方程：找到子问题之间的关系，写出dp[i]和之前状态的计算逻辑
- 确定遍历顺序：根据状态转移的依赖关系，确定dp数组的填充顺序
- 返回最终结果：根据状态定义取出对应位置的解作为答案
面试常考基础题目及PHP实现
1. 斐波那契数列
这是动态规划最入门的题目，要求计算第n个斐波那契数，规则是F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2）。
<?php
function fibonacci($n) {
// 边界条件处理
if ($n < 2) {
return $n;
}
// 定义dp数组，dp[i]表示第i个斐波那契数
$dp = array_fill(0, $n + 1, 0);
// 初始条件
$dp[0] = 0;
$dp[1] = 1;
// 状态转移，从2遍历到n
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = $dp[$i-1] + $dp[$i-2];
}
return $dp[$n];
}
// 测试调用，计算第10个斐波那契数
echo fibonacci(10);
?>
2. 0-1背包问题
题目描述：有N件物品和一个容量为W的背包，第i件物品的重量是weight[i]，价值是value[i]，每件物品只能选一次，求背包能装下的物品的最大价值。
<?php
function knapsack($weights, $values, $capacity) {
$n = count($weights);
// dp[i][j]表示前i件物品，背包容量为j时的最大价值
$dp = array_fill(0, $n + 1, array_fill(0, $capacity + 1, 0));
// 遍历物品
for ($i = 1; $i <= $n; $i++) {
// 遍历背包容量
for ($j = 1; $j <= $capacity; $j++) {
// 当前物品重量大于背包容量，无法放入
if ($weights[$i-1] > $j) {
$dp[$i][$j] = $dp[$i-1][$j];
} else {
// 选择放入或不放入，取最大值
$dp[$i][$j] = max($dp[$i-1][$j], $dp[$i-1][$j - $weights[$i-1]] + $values[$i-1]);
}
}
}
return $dp[$n][$capacity];
}
// 测试：3件物品，重量分别为2,3,4，价值分别为3,4,5，背包容量5
$weights = [2,3,4];
$values = [3,4,5];
$capacity = 5;
echo knapsack($weights, $values, $capacity);
?>
3. 最长公共子序列
题目描述：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。子序列不需要连续，但顺序必须一致。
<?php
function longestCommonSubsequence($text1, $text2) {
$m = strlen($text1);
$n = strlen($text2);
// dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
// 当前字符相同，长度加1
if ($text1[$i-1] == $text2[$j-1]) {
$dp[$i][$j] = $dp[$i-1][$j-1] + 1;
} else {
// 字符不同，取两种情况的最大值
$dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1]);
}
}
}
return $dp[$m][$n];
}
// 测试
echo longestCommonSubsequence("abcde", "ace");
?>
面试注意事项
在PHP动态规划面试中，除了写出正确的代码，还需要注意以下几点：首先要在写代码前先和面试官沟通清楚状态定义和转移逻辑，展示自己的思路；其次要注意边界条件的处理，比如n为0、数组为空的情况；最后可以尝试优化空间复杂度，比如斐波那契数列只需要保存前两个状态，不需要维护整个dp数组，这样能体现对算法的深入理解。