动态规划主题专杀-最长递增子序列-思路自我解剖

前言：做这种题再次强调一点，思路远比代码重要，思路对了，即使代码错了，错的也是细枝末节，思路错了，那就是个0.

所以本文并不想着重讲本题的算法代码，代码解法网上有得是。这里着重剖析自己的思路问题。

题干如下：

一直感觉自己对这种动态规划的状态转移方程的直觉很不好，亲自试了下这题，发现果然不好，上来就犯了两个错误。

第一，没有把状态转移中的状态函数定义好，后来看了答案（https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-she-ji-zui-chang-di-zeng-zi-xu-lie）发现状态转移函数人家是这样定义的：

“我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。”

而我自己起初想的是dp[i]代表从头到截止nums[i]这个元素这一段中的最长递增子序列的长度。

高下立判。

为什么答案中的更高？因为他定义的这个状态函数比我定义的范围要更明确，变数更小，物理学的角度看熵更低。为什么这么说？因为他的定义把子序列的一端给明确下来了，而我的定义，根本不包含子序列的任意一端，这就导致他的状态函数更有利于做递推，而我定义的状态函数很难做递推，果不其然，我就碰到了第二个问题：我尝试把dp(i)和dp(i-1)的递推关系找出来，结果找了半天发现根本找不到递推关系，一般这个时候，大脑就容易陷入死胡同，越想越乱。

当碰到第二个问题时，其实我犯了双重错误，第一重就是基于问题1而来，而第二重是我缺乏一个直觉，所谓的状态转移方程或者递推关系，根本不必拘泥于dp(i)到dp(i-1)，还可以包括更多啊，比如dp(i-2),dp(i-3)，其实仔细想想，fibonacci数列不就是这样的吗，算dp(i)是依赖于dp(i-1)和dp(i-2)的，由此可见，自以为理解了fibonacci数列，却仍不能灵活应用之，这就是理解的深度不够啊。

如果把这种向前多重依赖的思想真正内化了到自己脑子里，其实就不难发现这题的递推关系中，dp(i)实际上要依赖dp(i-1),dp(i-1)一直到dp(0)等一系列前序。

既然写到这里了，还是给一下代码吧：

public static int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    // dp 数组全都初始化为 1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        System.out.println("dp["+i+"]="+dp[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
}

动态规划主题专杀-最长递增子序列-思路自我解剖

相关推荐