LeetCode基础动态规划解题思路总结 - ZhangTory's NoteBlog - 张耀誉的笔记博客

LeetCode基础动态规划解题思路总结

首先不要被名字吓到或者骗到。
动态规划(Dynamic Programming),我以前一直在想这个“动态”和“规划”究竟是什么意思,后来发现纠结这个名字是没有意义的。
再后来总结了动态规划题目的步骤后,就能够意会“动态规划”的意思了。
先从LeetCode简单的动态规划入个门。

动态规划适用于能够把复杂问题分解为具有相同结构的子问题的题目。
和搜索不同在于,动态规划能够免去重叠子问题的计算,从而减少运行时间。
要实现动态规划必须确定一下3个关键点:

  1. 确定相同结构的最优子问题。
  2. 写出状态转移方程并确定边界条件。
  3. 写代码。
    其中最核心、最困难的是如何写出状态转移方程。

理解什么是动态规划

最基本的题目是斐波那契数
但是我当年学动态规划的时候却被斐波那契的各种解法搞晕了,所以我们换一个简单的题目:爬楼梯

首先是确定相同结构的最优子问题。
回到爬楼梯,求n级台阶有多少种方法,和n-1级台阶有多少种方法,可以用一个函数表示,我们用f(n)表示n级台阶的方法。
这样就把子问题给找到了。

然后需要列出状态转移方程,不要被这个名字吓到了,其实它就是一个数学问题。
首先f(n)肯定和f(n-1)有关系,但是有什么关系呢?是简单的+1还是+2?这就需要分析了。
我们可以把小规模的情况列一下,辅助我们找规律,同时还可以确定边界。
f(1)=1;f(2)=2;f(3)=3;f(4)=5;f(5)=8....
这样就很容看出规律了:f(n) = f(n-1) + f(n-2)

最后就是写代码。我们有递归和迭代2种方案来完成,本题是从底向上求解,那么迭代就更方便。
我们可以用一个数组来保存n从1到n时的方案数,这样空间复杂度为O(n);
但是根据状态转移方程,n只与n-1和n-2有关,我们可以直接定义两个变量用于保存f(n-1)和f(n-2)即可,空间复杂度可以降到O(1)。

public int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int sum = a + b;
        a = b;
        b = sum;
    }
    return b;
}

正式进入动态规划

爬楼梯只是让你了解思路,还算不上真正意义上的动态规划入门,现在来看看打家劫舍
看第一眼可能很懵逼,这怎么做啊?所以我们需要先确定子问题。
对于第一个房间,我们可以选择偷或者不偷;对于第二个房间,如果前一个房间没有偷,我们可以选择偷或者不偷,如果前一个房间偷了,那么我们只能选择不偷....
保安在哪里?保安...
哦不,是子问题在哪里?子问题呢?
确定子问题通常不会像爬楼梯那样能够直接看到,我们需要让思维跳跃一下。
1号房间偷了,2号就不能偷;想偷2号房间,1号房间就不能偷。
那么两种方案,哪种收益最大呢?当然是哪个房间的金币多就偷哪一个咯。
抽象一下,我们把n号房间的收益记为f(n),最大收益dp=max(f(1),f(2)),这是有2个房间的情况,我们记为dp[2]。
如果是3个房间,dp[3] = max(dp[2], f(3)+f(1))。
解释一下3个房间的最大收益取决于3号房间偷还是不偷。偷的话,收益就是3号+1号;不偷的话最大收益就是dp[2]的最大收益。
同理,dp[4] = max(dp[3], f[4]+dp[2])。
于是我们可以写出状态转移方程:dp[n] = max(dp[n-1], f(n)+dp[n-2]) 。
确定边界,0个房间的话dp[0] = 0,1个房间的话dp[1] = f(1),因为没得选。
然后从2个房间开始,就可以使用状态转移方程计算最大收益了。
然后就是写代码了。同样,我们只需要记住前2种状态就行了。

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        int a = 0, b = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int max = Math.max(b, nums[i]+a);
            a = b;
            b = max;
        }
        return b;
    }
}

动态规划进阶

再稍微难一点点的经典题目:最长上升子序列
这个题目在LeetCode上的难度为中等,但是非常经典。
很多动态规划题目都不能一眼明确状态,或者不能很轻松地推出状态状态转移方程,这种题目就不单单考我们的编程能力了,也同时在考思维能力。
如果我们认为dp[n]为有n个数的数组的最长的上升子序列的长度,他的子问题变成了dp[n-1]...思考一下,其实这样的话状态转移方程并不好写出,因为新的第n个数能否组成最长上升子序列是与之前的序列有关的,而与dp[n-1]关系不大。
这种就需要稍微变通一下,根据之前的分析,我们发现新加的第n个数非常关键,于是我们考虑定义dp[i]为以数组中n[i]结尾的最长上升子序列的长度。
如果新加入的第n个数比以dp[i]结尾的数n[i]大,那么加入第n个数后最大长度就为dp[i]+1。但是我们需要对dp[0]到dp[i]都检查一遍,取最大的dp值+1,因为可能出现1,2,666,999,3,4,5这样的情况。
当然如果新加入的第n个数是最小的,那么以他结尾的长度就为1。
最终求得状态转移方程: dp[i] = max(dp[j]) + 1 | 0 <= j < i, n[j] < n[i]

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    max = Math.max(dp[i], max);
                }
            }
        }
        return max;
    }
}

这里我定义了一个max作为全局最大长度,dp[i]默认为1,因为如果第i个数是最小的,则长度为1。
对于第i个数,需要从0到i-1依次比较,也就是j,如果第i个数大于第j个数,那么能够在以j结尾的序列上增加1个i。
同时这里维护了dp数组,记录状态。另外将dp[i]与max比较取最大值作为全局解。

添加新评论

电子邮件地址不会被公开,评论内容可能需要管理员审核后显示。