[动态规划] 四、最长递增子序列

题目

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。(LIS：longest increasing subsequence)
无序序列：5，3，4，8，6，7

动态规划问题建模阶段

设序列为 num[5,3,4,8,6,7]，最长递增子序列长度为 LIS

无序序列           |   5   3   4   8   6   7
—————————————————+—————————————————————————
前1个数的LIS长度   |   1
前2个数的LIS长度   |       1
前3个数的LIS长度   |           2
前4个数的LIS长度   |               3
前5个数的LIS长度   |                   3
前6个数的LIS长度   |                       4

规律：
  前1的LIS = 1，第一个是1
  前2的LIS = 1，3前面没有比3小的
  前3的LIS = 2，比4小的有3，3的长度+1 = 1+1
  前4的LIS = 3，比8小的有5 3 4，max(5的长度,3的长度,4的长度)+1
  ……
  最后的LIS = 4，比7小的有5 3 4 6

  由此可见，只需要存储前面的LIS，就可推出后面的LIS

动态规划三个重要的概念

最优子结构：
最后的7的LIS = max(前面小于7的数字的子序列长度)+1
边界：
当只有一个数时，LIS等于1
转态转移公式：
d(i) = max{1, d(j)+1}, 其中j<i,A[j]<=A[i]
例：d(4) = max( d(0), d(1), d(3) ) + 1

动态规划求解问题阶段

class Index 
{
    /**
     * 动态规划（Dynamic Programming）,这道题动态规划非最优解
     * 时间复杂度：O(n²)
     * 空间复杂度：O(n)
     */
    public function test()
    {
        $num     = array(5, 3, 4, 8, 6, 7);                       // 无序序列
        $num_len = count($num);
        $sub     = array_fill(0, $num_len, 1);  // 存放每个数的子序列长度,初始化为1

        // 循环 num 序列
        for ($i = 0; $i < $num_len; $i++) {
            // 循环当前数的前面数
            for ($j = 0; $j < $i; $j++) {
                // 如果当前数＞前面的数 && 当前数的LIS<前面数的LIS+1， 则更新当前数的LIS
                if ($num[$i] > $num[$j] && $sub[$i] < $sub[$j] + 1) {
                    $sub[$i] = $sub[$j] + 1;
                }
            }
        }
        $lis = max($sub);   // 最长非降子序列长度最大值
    }
}

参考：动态规划

本作品采用《CC 协议》，转载必须注明作者和本文链接