最长上升子序列
动态规划问题的解决需要找到重叠子问题和最优子结构，这个最长上升子序列问题，就是要找到i位置的数的上升子序列的长度，需要找到i之前的数j，即从位置0到i的区间里面的最长上升子序列的长度，如果比i位置的元素值小，那么加1就是i位置的最长子序列。
class Solution {
function lengthOfLIS($nums) {
$count = count($nums);
//空数组的最长子序列长度是0
if($count == 0){
return 0;
}
//初始每个位置的最长子序列长度是1
$lis = [];
foreach($nums as $k=>$val){
$lis[$k] = 1;
}
//从i=1个位置，考察最长上升子序列
for($i=1;$i<$count;$i++){
$max_flag = 0; //是否在[0,i)区间里面找到比i的值小的值。
$max = 1;
//在[0,i)区间里面找到i位置的最长上升子序列长度
//再根据之前找到的最长上升子序列长度，找到现在的最长上升子序列长度
//上面就是重叠子问题，通过自底向上的方式，解决问题，就是动态规划。
for($j=0;$j<$i;$j++){
//如果位置j的值小于当前位置i的值
if($nums[$j] < $nums[$i] ){
//当前的最长上升子序列长度和位置j的最长上升子序列长度的最大值
//附件介绍：当前位置i的最长上升子序列长度=1，还在计算中。
$max = max($max,$lis[$j]);
//$max就是i前面的最长上升子序列
$max_flag = 1;
}
//如果找到了比nums[$i]小的值，那么就需要位置i的最长上升子序列更新
if($max_flag == 1){
$lis[$i] = $max +1;
}
}
//内层for循环完成之后，就找到位置i的最长上升子序列的长度
}
//最后返回最大的，就是数组中，最长上升子序列的长度
return max($lis);
}
}
也可以简化为这样
class Solution {
function lengthOfLIS($nums) {
$count = count($nums);
if($count == 0){
return 0;
}
$lis = [];
foreach($nums as $k=>$val){
$lis[$k] = 1;
}
for($i=1;$i<$count;$i++){
for($j=0;$j<$i;$j++){
if($nums[$j] < $nums[$i] ){
//直接保存到lis[$i]，记录位置i最长上升子序列的长度
$lis[$i] = max($lis[$i],$lis[$j]+1);
}
}
}
//找到数组中最大的数
return max($lis);
}
}
