动态规划无非分为一下几步:找到“状态”和“选择”->明确DP数组/函数的定义->寻找“状态”之间的关系
最长递增子序列问题
首先要注意的是子串和子序列的区别,子串一定是连续的,而子序列不一定是连续的
首先引入数学归纳法的思路:假设这个结论在k<n时成立,然后根据这个假设,想办法推到证明出k=n的时候此结论也成立。如果能够证明出来,那么就说明这个结论对于k等于任何数都成立
那么对于最长递增子序列问题而言,我们首先要定义的是dp数组,dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度
假设目前已经知道了 dp[0...4]的所有结果,如何通过这些已知结果去推出dp[5]呢?
根据刚才对dp数组的定义,现在想求dp[5]的值,也就是想求以nums[5]为结尾的最长递增子序列
因为nums[5]为3,既然是递增子序列,只要找到前面那些结尾比3小的子序列,如何把3接进去,那么就可以形成一个新的子序列,而且这个新的子序列长度+1。
显然，可能形成很多新的子序列,但是只选最长的哪一个,把最长子序列的长度作为dp[5]的值即可
简化这一次过程的代码如下
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
当i等于5的时候,这段代码的逻辑就可以算出dp[5]了
那么在这里可能有个疑惑的地方,就是为什么要做这个dp[i]和dp[j+1]的选择呢?因为在每次遍历的时候dp[i]的值都是在变化的,因为数组是无序的,我们不能够确保每个元素的具体大小,因此只有每次都做一次推演,取极值才有可能得到正确的答案。
下面是完整代码
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
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++){
res = Math.max(dp[i],res);
}
return res;
}
}
当然了,我们可以看到尽管使用了动态规划,依然有两个非常刺眼的for循环,那么应该如何优化呢?
二分搜索解法
首先这个解法的例子我们可以看下:首先给你一排扑克牌,我们像遍历数组那样从左到右一张一张处理这些扑克牌,最终要把这些牌分成若干堆
处理这些扑克牌需要遵循以下规则:
只能把点数小的牌压到点数比它答或者和它相等的牌上
如果当前牌点数较大没有可以放置的堆,那么就新建一个堆,把这张牌放进去
如果当前牌有多个堆可供选择,则选择最左边的那一堆放置
如果按照上述的规则执行,那么就可以算出最长递增子序列了,牌的堆数就是最长递增子序列的长度
那么我们来回顾一下规则,首先,如果有个牌堆是可供选择的,那么选择最左边的那一堆放置,这就确保了一个特性,有序,有了这个特征,就可以使用二分搜索了,来看看解法:
class Solution {
public int lengthOfLIS(int[] nums) {
int piles = 0;
int[] TOP = new int[nums.length];
for(int i=0;i<nums.length;i++){
int poker = nums[i];
int left=0,right=piles;
//搜索最左侧边界,定义搜索区间为[left,right)
while(left < right){
int mid = (left+right)/2;
if(TOP[mid] > poker){
right = mid;
}else if(TOP[mid] < poker){
left=mid+1;
}else{
right = mid;
}
}
if(left == piles){
piles++;
}
TOP[left] = poker;
}
return piles;
}
}
信封嵌套问题
这道题相当于是二维的LIS问题,但是我们发现无法通过简单的数学计算将二维的数对转化为一维的数据
这道题的解法是比较巧妙的:首先对宽度w进行升序排序，如果遇到w相同的情况，则按照高度h降序排序。之后把所有的h作为一个数组，在这个数组上计算出的LIS的长度就是答案。
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(envelopes,new Comparator<int[]>()
{
public int compare(int[] a,int[] b){
return a[0] == b[0] ? b[1]-a[1] : a[0]-b[0];
}
});
int[] height = new int[n];
for(int i=0;i<n;i++){
height[i]=envelopes[i][1];
}
int[] dp = new int[height.length];
Arrays.fill(dp,1);
for(int i=0;i<dp.length;i++){
for(int j=0;j<i;j++){
if(height[i] > height[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
int res=0;
for(int i=0;i<dp.length;i++){
res = Math.max(res,dp[i]);
}
return res;
}
}
初步写出的代码,交上去之后发现超时,那么就可以采用我们之前所用的二分搜索法进行优化了
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(envelopes,new Comparator<int[]>()
{
public int compare(int[] a,int[] b){
return a[0] == b[0] ? b[1]-a[1] : a[0]-b[0];
}
});
int[] height = new int[n];
for(int i=0;i<n;i++){
height[i]=envelopes[i][1];
}
int[] top = new int[height.length];
int piles = 0;
for(int i=0;i<height.length;i++){
int poker = height[i];
int left = 0,right=piles;
while(left < right){
int mid = left+(right-left)/2;
if(poker > top[mid]){
left = mid+1;
}else if(poker < top[mid]){
right =mid;
}else {
right = mid;
}
}
if(left == piles){
piles++;
}
top[left]=poker;
}
return piles;
}
}
补充知识点
int [][]a = new int [5][2];
//定义一个二维数组，其中所包含的一维数组具有两个元素
对于一个已定义的二位数组a进行如下规则排序,首先按照每一个对应的一维数组第一个元素进行升序排序（即a[][0]）,若第一个元素相等,则按照第二个元素进行升序排序（a[][1]）。(特别注意,这里的a[][0]或者a[][1]在java中是不能这么定义的,这里只是想说明是对于某一个一维数组的第0或1个元素进行排序)
Arrays.sort(a, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0]==o2[0]) return o1[1]-o2[1];
return o1[0]-o2[0];
}
});
其中o1[1]-o2[1]表示对于第二个元素进行升序排序如果为o2[1]-o1[1]则表示为降序。
最大子数组问题
这道题让我想起了做的那道求最大子数组平均数的那道题,第一反应是滑动窗口,平均数那道题的收缩条件非常明确,因为定死了窗口的大小为k，那么窗口怎么扩大怎么缩小都是很明确的,但是对于这道题而言,我们没有办法知道什么时候去滑动窗口,因为存在着负数,扩展的时候有可能增加有可能减少,一旦减小了就不是最优解了,这么做的话就要回溯,可以说是相当不适合,但是可以使用动态规划来求解,用之前已经计算出的子数组来计算当前的子数组。
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
dp[0]=nums[0];
//dp数组的定义:以nums[i]为结尾的最大子数组和为dp[i]
for(int i=1;i<nums.length;i++){
dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);
}
int ans = Integer.MIN_VALUE;
for(int i=0;i<dp.length;i++){
ans = Math.max(ans,dp[i]);
}
return ans;
}
}
一般地,定义dp数组的通常的策略有以前i个元素为基准的数组值,以第i个元素为结尾的基准数组值
同时,也可以做一个状态压缩,在这道题里面,由于用来推算的值不涉及到多个元素,只涉及到dp[i-1]这个数值,所以可以用一个变量来替代数组,做一个状态压缩
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int dp_0=nums[0],dp_1=0,res=dp_0;
//要特别注意res的取值问题,由于res不在后面再做遍历求值了,因此默认最小值为第一个元素的值
for(int i=1;i<nums.length;i++){
dp_1=Math.max(dp_0+nums[i],nums[i]);
dp_0=dp_1;
res = Math.max(dp_1,res);
}
return res;
}
}
![【数据结构】 医院选址[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)