二次学习动态规划

最近在看一本经典的程序员书籍：《编程之美》，里面有一道买书的算法题，书中指导使用动态规划去解决该问题，虽然一年前有那么几天看似深入的学习了一下动态规划，但这次看完书上的解释之后还是不太清楚如何写代码去解决买书问题，所以用文章的方式再次记录一遍自己学习动态规划与解决买书问题的过程。

动态规划

动态规划是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，前面这句解释是从*摘录的，描述的相对简单，全文还有更为详细的解释，有兴趣的朋友可以看一下，不过看完后可能依旧云里雾里。

但知乎上的这个回答感觉是讲清了动态规划的本质，即寻找状态定义与状态转移方程，为了保证状态转移方程的正确性，可能需要严谨的证明过程，《编程之美》在买书问题上对动态规划解法着重讲解的就是状态转移方程的证明过程。

针对动态规划相关话题，自己只是门外汉，没有什么深刻的认识，故不做主观上的讲解，大家Google就好～

最长上升子序列

问题

最长上升子序列问题，算是动态规划话题的中的典型问题，理解起来不算特别复杂，问题描述：

给定一个数列，长度为N，求这个数列的最长上升（递增）子数列（LIS）的长度

以[1, 7, 2, 8, 3, 4]为例，这个数列的最长递增子数列是[1, 2, 3, 4]，长度为4

如果没有动态规划相关知识的话，这个问题还真不知道如何解决，哪怕看了一些动态规划的入门文章后，自己依旧想了几分钟，才明白应该如何用动手写代码。

状态定义与转移方程

针对动态规划问题，最重要的就是状态定义与状态转移方程：

• 状态定义

给定一个数列，长度为N

设F_k为：以数列中第k项结尾的最长递增子序列的长度

求F₁..F_N中的最大值

• 状态转移方程

F₁ = 1

F_k = max(F_i + 1 |A_k > A_i, i in (1..k-1))(k > 1)

如果看完上述状态定义和转移方程，依旧不理解如何解决问题，建议多看几遍，多思考几遍，然后你就通了。

状态定义不必多说，就是用数学的方式重新描述了一遍问题，但我认为这一步是有一定难度的，没有经验的人通常被卡在这一步。

如果状态定义不清楚，转移方程也就无从谈起，这两个是动态规划的核心，写代码跟这两个相比，就只是砌砖而已…

分析

状态转移方程决定了算法核心逻辑，针对数列list：[1, 7, 2, 8, 3, 4]，我们从F₁ = 1开始一步步推演：

• list[0] = 1，F(1)

F(1) = 1，当前状态：[1]

• list[1] = 7，F(2)

7 > 1 => F(2) = max(f(1)) + 1 = 2，当前状态：[1, 2]

• list[2] = 2，F(3)

2 > 1 => F(3) = max(f(1)) + 1 = 2，当前状态：[1, 2, 2]

• list[3] = 8，F(4)

8 > 1, 7, 2 => F(4) = max(f(1), f(2), f(3)) + 1 = 3，当前状态：[1, 2, 2, 3]

• list[4] = 3，F(5)

3 > 1, 2 => f(5) = max(f(1), f(3)) + 1 = 3，当前状态：[1, 2, 2, 3, 3]

• list[5] = 4，F(6)

4 > 1, 2, 3 => f(6) = max(f(1), f(3), f(5)) + 1 = 4，当前状态：[1, 2, 2, 3, 3, 4]

最终max(1, 2, 2, 3, 4) = 4，即最大升序子数列的长度。

代码实现

function maxLIS(nums) {
    nums = nums.map(item => [item, 0]); // [item, F(index)]，元素的值以及其对应的状态值

    nums.forEach((item, index) => {
        if (index === 0) {
            item[1] = 1;
            return;
        }

        // index之前且小于当前元素的列表
        let target = nums.slice(0, index).filter(one => one[0] < item[0]);
        let status = target.map(item => item[1]);

        item[1] = Math.max(...status) + 1;
    });

    return Math.max(...(nums.map(item => item[1])));
}

console.log(maxLIS([1, 7, 2, 8, 3, 4, 2])); // 4

买书问题

我还不够深入理解，写不出来…过两天，深入的时候再来写。

博客原文