动态规划问题

2020-03-09 本文已影响0人无知的talent

动态规划一般思路

动态规划的条件

无后效性
具备最优子结构

经典例题

背包问题（01背包，完全背包），丢鸡蛋问题，青蛙跳台阶问题，最长上升子序列

思考过程

判断是否满足dp解题的条件；
确定问题中的状态是什么
根据题目中的逻辑关系推导出状态转移方程
填充边界条件，也是初始化条件
思考是否可以进行剪枝操作或着动态规划数组的降维

LeetCode 198 打家劫舍

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例：
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解题

考虑所有的数字组合显然是不必要的，首先要分析如何找到最优解：

当n=1时， max_money(0) = nums[0]
当n=2时， max_money(1) = nums[1]
当n=3时，这时最优解有两种情况，一种是max_money(0)+nums[2]，一种是max_money(1)。因此 max_money(2) = max(max_money(0)+nums[2], max_money(1))

总结以上规律后就可以找到求解最优值的公式，也即动态规划的状态转移方程：
$max\_moeny(k)=max(max\_money(k-2)+nums[k],max\_money(k-1))$

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre_max = cur_max = 0
        for n in nums:
            tmp = cur_max
            cur_max = max(pre_max+n, cur_max)
            pre_max = tmp
        return cur_max

复杂度分析：

时间复杂度： $O(n)$

空间复杂度： $O(1)$

LeetCode300 最长上升子序列

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

解题

本题采用动态规划算法，首先看是否满足动态规划算法的两个条件。

第一，结果的无后效性，这一点显然是满足的，因为S(n)的最长子序列的结果，并不会影响到S(n+1)的最长子序列结果。

第二，就是寻找最优子结构，找到问题的最优子结构，我们就能找出状态转移方程。

首先，我们要明确这个问题中我们应该定义的状态，根据题意，我们可以定义状态为以当前数字为结尾的最长上升子序列。

然后我们要寻找状态方程，也即问题中的最优子结构，对于第i个数，我们可以根据nums[i]与nums[j] (j<i)之间的大小关系，求的dp[i]。因此有如下关系：
$dp[i]=max(m(j)) \ \ \ j<i\\ m[j] = dp[j]+1 \ if \ nums[i] > nums[j] \ else \ dp[i]$
在确定了状态转移方程之后，我们需要明确边界条件，在一开始时，所有的位置上的最长上升子序列长度都应该为1，即：
$dp[i]=1(i=[0:len(nums)])$
这样我们就完成了动态规划算法的设计，用python代码实现如下：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        l = len(nums)
        if not l:
            return 0
        
        dp = [1]
        
        for i in range(1,l):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

复杂度分析

时间复杂度：两重遍历， $O(n^2)$

空间复杂度： dp数组， $O(n)$