常见算法-动态规划

动态规划学习

动态规划

如果你不熟悉动态规划,请先点击这里参考。这篇博客是十分详细的,对于小白也完全适用。

动态规划的一般形式就是求最值,既然是求最值,那么其核心问题就是穷举。

动态规划的穷举有些特别,因为这类问题存在重叠子问题,为了避免暴力穷举导致的效率底下,我们需要备忘录来记录子问题的数值,来避免重复计算。

动态规划问题一定具有最优子结构,只有这样,才能够通过子问题的最值得到原问题的最值。要符合「最优子结构」,子问题间必须互相独立,若子问题之间相互牵扯,就不存在最优的问题。

另外,虽然动态规划的核心思想是穷举求最值,但是问题可以千变万化,为了进行正确合理的穷举,我们一定要列出正确的状态转换方程

总结以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

最优子结构

符合最优子结构的问题,可以从子问题的最优结果推出更大规模问题的最优结果。有一些问题不符合最优子结构,那也并不是一定不能够使用动态规划,我们只需要改造问题。换一种思路该将问题转变成可以利用最优子结构的问题即可。

最优子结构并不是动态规划独有的一种性质,能求最值的问题大部分都具有这个性质,但反过来,最优子结构性质作为动态规划问题的必要条件,一定是让你求最值得。

重叠子问题

三大步骤

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来进行保存,一般使用一维数组或者二维数组来保存。

步骤1:定义数组元素的含义。

步骤2:找出数组元素之间的关系式,也就是利用历史数据来推出新的元素值。

步骤3:找出初始值。

dp数组遍历方向

主要就是看 base case 和最终结果的存储位置,保证遍历过程中使⽤的数据都是计算完毕的就⾏,有时候确实存在多种⽅法可以得到正确答案,可根据个⼈⼝味⾃⾏选择。

动态规划的设计流程:

首先明确 dp 数组所存数据的含义。这步很重要,如果不得当或者不够清晰,会阻碍之后的步骤。

然后根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0...i-1] 都已知,想办法求出 dp[i],一旦这一步完成,整个题目基本就解决了。

但如果无法完成这一步,很可能就是 dp 数组的定义不够恰当,需要重新定义 dp 数组的含义;或者可能是 dp 数组存储的信息还不够,不足以推出下一步的答案,需要把 dp 数组扩大成二维数组甚至三维数组。

最后想一想问题的 base case 是什么,以此来初始化 dp 数组,以保证算法正确运行。

典型例题

最长递增子序列

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

解析

首先明确 dp 数组所存数据的含义。这步很重要,如果不得当或者不够清晰,会阻碍之后的步骤。

然后根据 dp 数组的定义,运用数学归纳法的思想,假设 $dp[0…i-1]$ 都已知,想办法求出 $dp[i]$,一旦这一步完成,整个题目基本就解决了。

但如果无法完成这一步,很可能就是 dp 数组的定义不够恰当,需要重新定义 dp 数组的含义;或者可能是 dp 数组存储的信息还不够,不足以推出下一步的答案,需要把 dp 数组扩大成二维数组甚至三维数组。

最后想一想问题的 base case 是什么,以此来初始化 dp 数组,以保证算法正确运行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 给定一个无序的整数数组,寻找最长递增子序列
* dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
* @author x1aolin
*
*/
public class LeetCode300 {
//时间复杂度:O(n2)
public static int lengthOfLIS(int[] nums) {
//dp[i]表示选择nums[i]为结尾的最长递增子序列
//最后我们只需要找出dp[i]中的最大值即可
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);;
for(int i=1;i<nums.length;i++){
//int j=0;j<i;j++ 这样也可以
for(int j=i-1;j>=0;j--){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[j]+1, dp[i]);
}
}
}
int max = 0;
for(int tmp:dp){
max = Math.max(max, tmp);
}
return max;
}
}

当然,这代码可以再优化,这里就不再说了。

编辑距离

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------