PHP动态规划实现0-1背包与最长上升子序列：前者用二维数组dpi记录前i个物品在容量j下的最大价值，后者用一维dp[i]表示以nums[i]结尾的最长上升子序列长度。
PHP实现动态规划经典问题，需围绕具有重叠子问题和最优子结构特征的典型场景展开。以下是针对多个经典问题的独立实现方法：
一、0-1背包问题
该问题要求在总容量约束下选择若干物品，使总价值最大，每个物品仅能选或不选。核心在于构建二维状态数组，记录前i个物品在容量j下的最大价值。
1、定义物品重量数组$weights和价值数组$values，以及背包总容量$capacity。
2、初始化二维数组$dp，维度为[count($weights)+1][$capacity+1]，所有元素初值设为0。
立即学习“PHP免费学习笔记（深入）”；
3、外层循环遍历物品索引$i从1到count($weights)，内层循环遍历容量$j从0到$capacity。
4、若当前物品重量$weights[$i-1]大于$j，则$dp[$i][$j] = $dp[$i-1][$j]；否则取$max($dp[$i-1][$j], $values[$i-1] + $dp[$i-1][$j - $weights[$i-1]])。
5、最终结果为$dp[count($weights)][$capacity]，即所有物品参与决策后在满额容量下的最大价值。
二、最长上升子序列（LIS）
目标是找出数值序列中最长的严格递增子序列长度。动态规划通过逐元素扩展可能的上升路径，避免重复枚举所有子序列。
1、声明数组$dp，长度与输入数组$nums相同，每个$dp[$i]初始化为1，表示单个元素构成长度为1的上升序列。
2、对每个位置$i从1开始遍历，再嵌套遍历$j从0到$i-1。
3、当$nums[$j]
4、遍历完成后，$dp数组中的最大值即为所求长度，无需回溯构造具体序列即可获得最优解值。
三、斐波那契数列（自底向上填表法）
递归求解存在大量重复子调用，动态规划采用迭代方式顺序计算并缓存中间结果，将时间复杂度由指数级降至线性级。
1、若$n ≤ 1$，直接返回$n$。
2、声明数组$fib，长度为$n+1$，令$fib[0] = 0$，$fib[1] = 1$。
3、使用循环从$i = 2$至$i = n$，依次计算$fib[$i] = $fib[$i-1] + $fib[$i-2]。
4、返回$fib[$n]，该值代表第n项斐波那契数，且全程无函数调用开销。
四、编辑距离（Levenshtein Distance）
衡量两个字符串相互转换所需的最少单字符操作次数（插入、删除、替换）。状态转移依赖于末尾字符是否相等，并参考左、上、左上三个相邻状态。
1、设$str1长度为$m，$str2长度为$n$，创建二维数组$dp，维度为[$m+1][$n+1]。
2、初始化边界：$dp[$i][0] = $i（删完$str1前$i字符），$dp[0][$j] = $j（插入$str2前$j字符）。
3、双重循环遍历$i从1到$m，$j从1到$n$；若$str1[$i-1] == $str2[$j-1]，则$dp[$i][$j] = $dp[$i-1][$j-1]；否则$dp[$i][$j] = min($dp[$i-1][$j]+1, $dp[$i][$j-1]+1, $dp[$i-1][$j-1]+1)。
4、结果为$dp[$m][$n]，即两字符串完全匹配所需最小操作总数。
五、最长公共子序列（LCS）
寻找两个字符串共有的最长子序列（字符顺序一致但不必连续）。状态定义为$dp[$i][$j]表示$str1前$i字符与$str2前$j字符的LCS长度。
1、初始化二维数组$dp，维度为[strlen($str1)+1][strlen($str2)+1]，全置0。
2、双重循环$i从1到strlen($str1)，$j从1到strlen($str2)。
3、若$str1[$i-1] == $str2[$j-1]，则$dp[$i][$j] = $dp[$i-1][$j-1] + 1；否则$dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1])。
4、最终值$dp[strlen($str1)][strlen($str2)]即为两字符串最长公共子序列的字符数量。
