记录生活中的点点滴滴

0%

动态规划刷题

记录一下前些天刷leetcode上面的动态规划的题,便于后续复习!

leetcode 494 目标和

https://leetcode-cn.com/problems/target-sum/

给定这么一个数组,我们通过添加符号确定可以让数组和与S相等的方法数。

最简单的就是不断枚举,复杂度为2的n次方那种。

但是怎样去实现这种最简单的枚举呢?

我们可以通过递归去实现,具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//最基本的递归求解,时间复杂度为2^n
public class Demo1 {
static int sum = 0;
public static void main(String[] args) {
System.out.println(findTargetSumWays(new int[]{1,1,1,1,1}, 3));
}
public static int findTargetSumWays(int[] nums, int S) {
if(nums.length==0) return 0;
calc(nums,0,S);
return sum;
}

private static void calc(int[] nums, int i, int s) {
if(nums.length==i){
if(s==0){
sum++;
}
return;
}
calc(nums,i+1,s+nums[i]);
calc(nums,i+1,s-nums[i]);
}
}

第二种方法借助一个dp数组,进行动态规划求解。

思路:

  1. 01背包问题是选或者不选,但本题是必须选,是选+还是选-。先将本问题转换为01背包问题。
    假设所有符号为+的元素和为x,符号为-的元素和的绝对值是y。
    我们想要的 S = 正数和 - 负数和 = x - y
    而已知x与y的和是数组总和:x + y = sum
    可以求出 x = (S + sum) / 2 = target
    也就是我们要从nums数组里选出几个数,令其和为target
    于是就转化成了求容量为target的01背包问题 =>要装满容量为target的背包,有几种方案
  2. 特例判断
    如果S大于sum,不可能实现,返回0
    如果x不是整数,也就是S + sum不是偶数,不可能实现,返回0
  3. dp[j]代表的意义:填满容量为j的背包,有dp[j]种方法。因为填满容量为0的背包有且只有一种方法,所以dp[0] = 1
  4. 状态转移:dp[j] = dp[j] + dp[j - num],
    当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数
    也就是当前数num的加入,可以把之前和为j - num的方法数加入进来。
  5. 返回dp[-1],也就是dp[target]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for(int i=0;i<nums.length;i++)
sum += nums[i];

if(S>sum || ((sum+S)&1)==1)
return 0;
int target = (sum+S)/2;
int[] dp = new int[target+1];
dp[0] = 1;
for(int num : nums){
for(int j=target;j>=num;j--)
dp[j] = dp[j] + dp[j-num];
}
return dp[target];
}
}

leetcode 72 编辑距离

从后面双指针遍历两个字符串,相等的话:i-1 j-1。不相等的话,无非就三种情况:删除i下标那个、删除j下标那个、或者替换。找到最小的那个就可以,所以先用递归去解决这个问题:

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
29
30
//递归求解
public class Demo1 {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
return backTrack(word1,word2,l1-1,l2-1,0);
}
//递归函数
public int backTrack(String s1,String s2,int i,int j,int count){
//base case
if(i==-1 && j==-1)
return count;
if(i==-1)
return backTrack(s1,s2,i,j-1,count+1);
if(j==-1)
return backTrack(s1,s2,i-1,j,count+1);
if(s1.charAt(i)==s2.charAt(j)){
return backTrack(s1,s2,i-1,j-1,count);
}else{
return getMin(
backTrack(s1,s2,i,j-1,count+1),
backTrack(s1,s2,i-1,j,count+1),
backTrack(s1,s2,i-1,j-1,count+1));
}
}
//比较三个数最小的
public int getMin(int x1,int x2,int x3){
return Math.min(x1,x2)>x3 ? x3 : Math.min(x1,x2);
}
}

然后这个其实是很多子问题想堆结而来,所以可以去剪纸,利用bp数组去完成。

想象成一个数组,迭代去填充它,最后返回我们所需要的值即可。

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
29
30
31
32
33
package cn.gs.p72;

public class Demo2 {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
int[][] dp = new int[l1+1][l2+1];
for(int i=0;i<=l1;i++){
dp[i][0] = i;
}
for(int j=0;j<=l2;j++){
dp[0][j] = j;
}
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = getMin(
dp[i-1][j]+1,
dp[i][j-1]+1,
dp[i-1][j-1]+1
);
}
}
}
return dp[l1][l2];
}
//比较三个数最小的
public int getMin(int x1,int x2,int x3){
return Math.min(x1,x2)>x3 ? x3 : Math.min(x1,x2);
}
}

leetcode 300 最长递增子序列

方法:动态规划(这是使用动态规划解决的一个经典问题)

明确题目中的条件:

  • 子序列:不要求连续子序列,只要保证元素前后顺序一致即可;
  • 上升:这里的「上升」是「严格上升」,例如: [2, 3, 3, 6, 7] 这样的子序列是不符合要求的。

题目只问最长上升子序列的长度,没有问最长上升子序列是什么,因此考虑使用动态规划。

第 1 步:状态定义。dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。即:在 [0, ..., i] 的范围内,选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。

说明:以 nums[i] 结尾,是子序列动态规划问题的经典设计状态思路,思想是动态规划的无后效性(定义得越具体,状态转移方程越好推导)。

第 2 步:推导状态转移方程:遍历到 nums[i] 的时候,我们应该把下标区间 [0, ... ,i - 1]dp 值都看一遍,如果当前的数 nums[i] 大于之前的某个数,那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的数都看了, dp[i] 就是它们的最大值加 $1$。即比当前数要小的那些里头,找最大的,然后加 $1$ 。

状态转移方程即:dp[i] = max(1 + dp[j] if j < i and nums[j] < nums[i])

第 3 步:初始化。单独一个数是子序列,初始化的值为 1;

第 4 步:输出。应该扫描这个 dp 数组,其中最大值的就是题目要求的最长上升子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = 1;
int res = 1;
for(int i=1;i<len;i++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
res = Math.max(dp[i],res);
}
return res;
}
}

第二种方法就是生成一个res数组。因为我们最后要求的数组肯定是依次递增的,我们可以先迭代nums数组,然后把能递增的序列按顺序添加到res数组中,并定义一个len,作为res数组的假定长度,也就是我们最后要返回的值,即序列长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int lengthOfLIS(int[] nums) {
int numLen = nums.length;
int[] res = new int[numLen];
//初始化res数组和len结果值
res[0] = nums[0];
int len = 1;
for(int i=1;i<numLen;i++){
int j;
for(j=0;j<len;j++){
if(nums[i]<=res[j])
break;
}
if(j<len){//说明遇到了小于等于的情况,替换即可
res[j] = nums[i];
}else{//说明没有遇到小于的情况,这样要len++
res[len++] = nums[i];
}
}
return len;
}
}

这个代码中,我们的查找是 for(j=0;j<len;j++){ 这样迭代去查找,当然我们也可以用二分查找,这样可以减小复杂度。代码如下:

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
29
30
31
32
class Solution {
public int lengthOfLIS(int[] nums) {
int numLen = nums.length;
int[] res = new int[numLen];
//初始化res数组和len结果值
res[0] = nums[0];//len数组只能是单调递增的,不能有相等的,那么最后它的长度就是我们需要返回的数
int len = 1;
for(int i=1;i<numLen;i++){

int left = 0;
int right = len;
while (left<right){
int mid = (left+right)/2;
if(nums[i]<res[mid]){
right = mid;
}else if(nums[i]>res[mid]){
left = mid+1;
}else{
left = mid;
break;
}
}

if(left<len){//说明遇到了小于等于的情况,替换即可
res[left] = nums[i];
}else{//说明没有遇到小于的情况,这样要len++
res[len++] = nums[i];
}
}
return len;
}
}

leetcode 354 俄罗斯套娃信封问题

这道题的思想和前面求最长递增子序列思想差不多,这个要更难一点。根据宽度我们去排序,但是高度那一行怎么说,如果宽度相等的话,高度需要递减,因为高度相等就说明不能继续套娃了。所以排序的话就可以按照宽度升序,相等的宽度的话高度降序这样的规则去排序,然后高度那一列组成一个数组,求这个数组的最长递增序列就可以了。

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
29
30
31
32
33
34
35
36
class Solution {
public int maxEnvelopes(int[][] arr) {
int len = arr.length;
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]==o2[0] ? o2[1]-o1[1] : o1[0]-o2[0];
}
});
int[] newArr = new int[len];
for (int i = 0; i < len; i++) {
newArr[i] = arr[i][1];
}
return lengthOfLIS(newArr);
}
public int lengthOfLIS(int[] nums) {
int numLen = nums.length;
int[] res = new int[numLen];
//初始化res数组和len结果值
res[0] = nums[0];
int len = 1;
for(int i=1;i<numLen;i++){
int j;
for(j=0;j<len;j++){
if(nums[i]<=res[j])
break;
}
if(j<len){//说明遇到了小于等于的情况,替换即可
res[j] = nums[i];
}else{//说明没有遇到小于的情况,这样要len++
res[len++] = nums[i];
}
}
return len;
}
}

leetcode 53 最大自序和

用bp求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
//通俗易懂的dp
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for(int i=1;i<nums.length;i++){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>max)
max = dp[i];
}
return max;
}
}

当然,bp数组的一个数只与它前面一个相关,所以可以把数组变成一个数,来减少空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum = 0;
for(int num : nums){
if(sum>0)
sum+=num;
else
sum=num;
res = Math.max(res,sum);
}
return res;
}
}

leetcode 1143 最长公共子序列

和编辑距离差不多,借助一个bp二维表就可以解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int l1 = text1.length();
int l2 = text2.length();
int[][] dp = new int[l1+1][l2+1];
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+1;
}else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[l1][l2];
}
}

leetcode 518 零钱兑换

老方法,先定义dp二维数组,确定它的含义,然后去找到递推关系和base case,直接贴代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int change(int amount, int[] coins) {
//dp[i][j]表示只使用coins中前i个硬币凑出金额j有dp[i][j]种方法
int count = coins.length;
int[][] dp = new int[count+1][amount+1];
for(int i=0;i<=count;i++)
dp[i][0] = 1;
for(int i=1;i<=count;i++){
for(int j=1;j<=amount;j++){
if(j>=coins[i-1])
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[count][amount];
}

然后其实这样发现每一次 dp [i] [j] 只与它前一位 dp [i-1] [..] 相关联,所以可以把二维数组变换成一维数组来压缩空间。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
//空间压缩优化
public int change(int amount, int[] coins) {
int count = coins.length;
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i=1;i<=count;i++){
for(int j=coins[i-1];j<=amount;j++){
dp[j] += dp[j-coins[i-1]];
}
}
return dp[amount];
}

leetcode 416 分割等和子集

这题和上题的背包问题其实差不多,这个说的是分割等和子集,其实就是看能不能凑出来 sum/2 和的一个子集,但是还有一点就是不能重复,只能用一次。所以还是dp二维表,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canPartition(int[] nums) {
//明确dp数组 dp[i][j]表示前i个nums中能否凑出j,boolean变量
int len = nums.length;
int sum = 0;
for(int i=0;i<len;i++)
sum+=nums[i];
if(sum%2==1)
return false;
sum = sum/2;
boolean[][] dp = new boolean[len+1][sum+1];
for(int i=0;i<=len;i++){
dp[i][0] = true;
}
for(int i=1;i<=len;i++){
for(int j=1;j<=sum;j++){
if(nums[i-1]>j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
return dp[len][sum];
}

看看上面代码还是可以优化的,把二维表转换成一维表,唯一需要注意的是 j 应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//对空间进行压缩,变成一维数组
public boolean canPartition(int[] nums) {
//明确dp数组 dp[i][j]表示前i个nums中能否凑出j,boolean变量
int len = nums.length;
int sum = 0;
for(int i=0;i<len;i++)
sum+=nums[i];
if(sum%2==1)
return false;
sum = sum/2;
boolean[] dp = new boolean[sum+1];
dp[0] = true;
for(int i=1;i<=len;i++){
for(int j=sum;j>=nums[i-1];j--){
dp[j] = dp[j] || dp[j-nums[i-1]];
}
}
return dp[sum];
}

leetcode 435 无重叠区间

做这道题之前,我们先看一个类似的题目:

给你很多形如 [start, end] 的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间

1
int intervalSchedule(int[][] intvs) {}

举个例子,intvs = [[1,3], [2,4], [3,6]],这些区间最多有 2 个区间互不相交,即 [[1,3], [3,6]],你的算法应该返回 2。注意边界相同并不算相交。

这个问题在生活中的应用广泛,比如你今天有好几个活动,每个活动都可以用区间 [start, end] 表示开始和结束的时间,请问你今天最多能参加几个活动呢?显然你一个人不能同时参加两个活动,所以说这个问题就是求这些时间区间的最大不相交子集。

正确的思路其实很简单,可以分为以下三步:

  1. 从区间集合 intvs 中选择一个区间 x,这个 x 是在当前所有区间中结束最早的(end 最小)。
  2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
  3. 重复步骤 1 和 2,直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

把这个思路实现成算法的话,可以按每个区间的 end 数值升序排序,因为这样处理之后实现步骤 1 和步骤 2 都方便很多:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int intervalSchedule(int[][] intvs) {
if (intvs.length == 0) return 0;
// 按 end 升序排序
Arrays.sort(intvs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// 至少有一个区间不相交
int count = 1;
// 排序后,第一个区间就是 x
int x_end = intvs[0][1];
for (int[] interval : intvs) {
int start = interval[0];
if (start >= x_end) {
// 找到下一个选择的区间了
count++;
x_end = interval[1];
}
}
return count;
}

有了这道题的求解,我们现在来看上面没做的那道题目。其实和刚刚那道题思路一样,不过最后求出count,不是要返回的值,而用length去减去count才是要返回的值。

所以解题代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length==0)
return 0;
//先按照end进行升序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
//排序后至少有一个不相交
int count = 1;
//先从第一个开始
int pivot = intervals[0][1];
for (int[] interval : intervals) {
if(interval[0]>=pivot){
count++;
pivot = interval[1];
}
}
return intervals.length-count;
}

这两道题的思想就是贪心思想,贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别的时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。

什么是贪心选择性质呢,简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一部分问题拥有这个性质。

OK,接下来再做一道类似的贪心题。

leetcode 452 用最少数量的箭引爆气球

这次只是稍微把区间规定了一下,本来我们判断语句是 interval[0]>=pivot ,因为如果相同也会射爆,所以要改成 interval[0]>pivot 就去下一个迭代算count就可以了。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findMinArrowShots(int[][] points) {
if(points.length==0)
return 0;
//先按照end进行升序
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1],o2[1]);
}
});
//排序后至少有一个不相交
int count = 1;
//先从第一个开始
int pivot = points[0][1];
for (int[] point : points) {
if(point[0]>pivot){
count++;
pivot = point[1];
}
}
return count;
}