动态规划解题思路
发布时间:2020-01-06 03:46

图片 1

算法能力就是程序员的内力,内力强者对编程利剑的把控能力就更强。

数键盘

动态规划就是,通过递推的方式,由最基本的答案推导出更复杂答案的方法,直到找到最终问题的解。或者是,通过递归的方式,将复杂问题化解为更简单问题的方法,直到化解为有明确答案的最基础问题。

问:你现在用的键盘上有多少个键帽?

当我问你这个问题时,你一定想到了解决方案,一个个数肯定能得到答案。

我们可以把这个简单的问题,用公式定义的更加清楚:设 F(n) 为键帽的总数,求 F(n) 的值。当你开始数第一个的键帽的时候,你得到了 F(1) = 1,这是一个最基本的答案。数数过程中,下一个答案等于上一个答案加 1。在状态规划中,我们通常把阶段性的答案,称作状态。复杂状态与简单状态之间存在的转化关系,叫做状态转移方程,状态转移方程是动态规范的核心,这这道题目中就是:

F(i) = F(i-1) +1(0i≤N)

当我们使用递推的方式,来求解动态规划时,我们会从 1 开始数起,一步步累加得到最终的状态:

F(1) = 1F(2) = F(1) + 1...F(N) = f(N-1) + 1

当我们使用递归的方式,来求解动态规划时,我们会从把所有的键帽数量,记作状态 F(N),当我们数了一个键帽后,那么 剩下的状态就记作 F(N-1),因此:

F(N) = F(N-1) + 1F(N-1) = F(N-2) + 1...F(1) = 1

无论是递推还是递归,都是得到的答案无疑都是一样的,只不过思维的方式有些不一样。递推是正向思维,先有基础答案后由复杂答案,最后得出最终问题的答案。递归是逆向思维,先有复杂的问题,然后把它化解为更简单的问题,直到分解为能一眼看出答案的基本问题。

数键盘虽然是一个很简单的游戏,但是解答的过程中已经包含了最基础的动态规划解题思路:

定义状态再重新定义问题找到最基础的状态找出状态转移方程编程求解最长上升子序列

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

示例:

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

说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。

这道题目的问题是,求最长上升子序列的长度。直接拿到这个问题,肯定一脸懵逼,最长上升子序列的长度是什么?断词断句一个个解释,序列、子序列、上升序列、最长上升子序列的长度。

序列:这里指的是,一个无序的整数数组。

子序列:将原序列中的部分值,重新组合成一个新的序列,这个新的序列就是子序列。一个序列可以有多个子序列。如,原序列 [1, 5, 2, 3],那么 [1, 5] 和 [1, 2, 3] 都是原序列的子序列。

上升序列:从前往后看,序列中的前面的数字比后面的数字更小,序列呈递增规律,就是上升序列。[1, 2, 3] 就是上升序列,[1,2,0] 就不是上升序列。

最长上升子序列的长度:一个序列可能会有多个上升子序列,其中长度最长的叫做最长上升子序列,其长度叫做最长上升子序列的长度。

动态规划方法一

第一步:定义状态。定义状态为,以当前序列第 i 个数字结尾的最长上升子序列的长度,记作 L(i),0≤i≤N-1,N为序列长度。示例:序列[1,2,3],状态 L[1] = 2 ,表示第 1 个以 2 结尾的最长上升子序列的长度为 2。

第二步:重新定位问题。序列中的最长上升子序列,不一定是以最后一个数字结尾,而是所有状态中的最大值,即 Math.max(L[0],L[1],…,L(N-1))。示例:[1,2,0] 的最长上升子序列是 [1,2] ,是以第1个数字结尾的。

第三步:找到最基础的状态。当序列为空时,结尾的最长上升子序列的长度为0。但是我们发现,最初我们定义的状态,并不能表示该最基础的状态,因此需要对状态的定义稍作修正。

状态:以当前序列第 index 个数字结尾的最长上升子序列的长度,index 是序列的下标,记 i = index + 1 ,状态为 L(i),0≤i≤N,N为序列长度。此时 L[0] 表示空序列的最长上升子序列的长度 L[0] = 0,L[1] 表示以序列中第 0 位数字结尾的最长上升子序列的长度,L[1] = 1。

第四步:找到状态转移方程。若 L[i] 大于 1,则 L[i] 表示的子序列,去掉最后一位数,依旧是一个子序列,记该子序列为 L[j] 。其关系为 L[i] = L[j] + 1 。其中 L[j] 的最后一位 nums[j -1] nums[i - 1],且 L[j] = Math.max( L[1],…,L[i-1]) ,0ji。

例如:序列A [1, 2, 6, 3, 4]

1. L[0] = 02. L[1] = 13. L[2] = Math.max( L[1]) + 1 = L[1] + 1 = 2, 其中 nums[1-1]  nums[2-1] 4. L[3] = Math.max(L[1], L[2]) + 1 = L[2] + 1 = 2, 其中 nums[2-1]  nums[3-1] 5. L[4] = Math.max(L[1], L[2],L[3]) + 1 = L[2] + 1 = 2, 其中 nums[2-1]  nums[4-1] 6. L[5] = Math.max(L[1], L[2],L[3],L[4]) + 1 = L[4] + 1 = 2, 其中 nums[4-1]  nums[5-1] 

变成为:

function lengthOfLIS(nums) { const dp = [0] for (let i = 1; i = nums.length; i++) { let max = 0 for (let j = 1; j  i; j++) { if (nums[j - 1]  nums[i - 1]) { max = Math.max(max, dp[j]) } } dp[i] = max + 1 } return Math.max(...dp)};

动态规划方法二

第一步:定义状态。在序列前 index 项中,所有可能成为最长上升子序列的子序列。S[i]

示例:A [10, 1, 12, 2, 3]S[0] = [[10]]S[1] = [[10], [1]]S[2] = [[10, 12], [1, 12]]S[3] = [[10, 12], [1, 12], [1, 2]]S[4] = [[10, 12], [1, 12], [1, 2, 3]]

当 S[1] = [[10], [1]] 时,A[2] 存在三种情况,①当 10 A[2] 时, [10, A[2]] 和 [1, A[2]] 表示的长度等价;②当 1 A[2] ≤ 10 时, [1, A[2]] 比 [10] 长;③当 A[2] ≤ 1 时,S[3] = [[10], [1], A[3]]。

因为题目只需要返回最终长度,所以 [10] 或 [1] 两种情况实际,可以简写为 [1] 这一种情况。A[3] 存在 3中情况,分别为①当 10 A[2] 时, [1, A[2]] ;②当 1 A[2] ≤ 10 时, [1, A[2]];③当 A[2] ≤ 1 时,S[3] = [A[3]]。因此可证明,只保留 [1] 一种情况,实际上已经代表了 [10] 或 [1] 两种情况。

对状态进行重新定义:在序列前 i 项中,长度为 k 的上升子序列中,最后一位的最小值。S[i]

示例:A [10, 1, 12, 2, 3]S[0] = [10]S[1] = [1]S[2] = [1,12]S[3] = [1,2]S[4] = [1,2,3]

第二步:重新定位问题。 求 S[N-1] 的长度,其中 N 为序列的长度。

第三步:找到最基础的状态。当序列为空时,结尾的最长上升子序列的长度为0,因此对问题和状态进行重新修正。

状态:在序列前 i + 1 项中,长度为 k 的上升子序列中,最后一位的最小值。S[i]

问题:求 S[N] 的长度,其中 N 为序列的长度。

第四步:找到状态转移方程。如果 A[i-1] 比 S[i] 最后一位还要大,记作 S[i][len -1] A[i-1] ,即可以组成一个更长子序列,s[i] = [...s[i -1],A[i-1]]。如果 A[i-1] 比 S[i] 中某一位 S[i][j]要小,但是比该位的前一位 S[i][j-1]要大,更具第一步中的推论,可以用 A[i-1] 替换掉 S[i][j] ,S[i] = […,S[i][j-1],A[i-1] ,…]

示例:A [10, 1, 12, 2, 3]S[0] = [] // 初始化S[1] = [10] // 在最后添加 A[1-1]=10S[2] = [1] // A[2-1]  S[2][0],因此替换掉 S[2][0]S[3] = [1,12] // 在最后添加 A[3-1]= 12S[4] = [1,2] // S[2][0]  A[2-1]  S[2][1],因此替换掉 S[2][1]S[5] = [1,2,3] // 在最后添加 A[5-1]= 3

实现:

function lengthOfLIS(nums) { const sequence = [] // 复杂度 n for (let i = 1; i = nums.length; i++) { let len = sequence.length // 增加 if (sequence[len - 1]  nums[i-1]) { sequence[len] = nums[i-1] // 替换 } else { // sequence 具有单调性,可以使用 logn 复杂度的二分查找,查找到 S[i][j-1]A[i]=S[i][j] (0≤j≤i) 的位置,并对 S[i][j] 进行重新赋值。 let target = nums[i-1] let start = 0 let end = len let mid = parseInt(len / 2) let x = 0 while (start = end) { if (target === sequence[mid]) { x = mid break } else if (sequence[mid]  target) { x = mid + 1 start = mid + 1 mid = parseInt((start + end) / 2) } else { x = mid end = mid - 1 mid = parseInt((start + end) / 2) } } sequence[x] = nums[i-1] } } return sequence.length};

来自: