C++ 吃透动态规划算法

本文需要花费半天乃至一天的时间来学习, 前提内功深厚, 不然一时半会还真看不懂
觉得有用给个三连呗 !!!

1. 介绍

• 动态规划 (Dynamic Programming, DP)
• 保存子问题, 避免重复计算
• 关键是: 找到转移方程, 确定边界条件, 明确dp数组含义
• 比如我们熟悉的斐波那契数列, 其实dp跟递归是一样的, 只是因为递归占用时间和空间较大, 所以尽可能使用dp解题, 事半功倍.

int feiB(int n){
	if(n<=1) return n;
	vector<int>dp(n+1, 0); //多出来一个, 因为feiB(3) = 2
	dp[0]=0, dp[1]=1;  // 边界条件
	for(int i=2; i<=n; i++){ 
		dp[i] = dp[i-1]+dp[i-2]; // 转移方程
	}
	cout<<n<<"的结果是"<<dp[n]<<endl;
	return dp[n];
}
1
2
3
4
5
6
7
8
9
10

2. 子序列问题

解题思路:

1. 思考问题能不能转化成树的形式
2. 思考树是不是自底向上求取结果
3. 根据这个树, 确定自底向上的关系式, 比如上层节点A = 下层节点(A1+A2)
4. 具体操作见下面的示例图解

这部分问题, 笔试面试的时候出的特别多, 因为这部分问题如果有思路, 很快就能确定解决方案, 并且代码量不多, 只需要理解动态规划就会很好写, 具体的题目见下面, 对于前两个题两个题太重要了, 一定要牢牢掌握住, 为后面的笔试面试奠基牢固的基础, 因为第三个题往后都是这两个题的延伸延伸延伸.

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
1
2
3
4
5
6
7
8
9

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int m=s1.size(), n=s2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 默认dp[i][j](0,0) = 0
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s1[i-1] == s2[j-1]){ // 字符串索引从0开始, dp[1][1]表示s1[0]和s2[0]公共子序列
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
输入：nums = [0,1,0,3,2,3]
输出：4
1
2
3
4
5

由上图可知, 比如第4个位置对应的最长递增子序列, 其结果跟前三个位置都相关

class Solution {
public:
    // 可能是动态规划, 从底层往上层走, 发现4跟123有关, 即4是123其中最大值加一如果4大于123
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n=nums.size();
        
        vector<int> dp(n, 1); // 只要数组不空, 递增子序列最差也是1
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        // print_v(dp);
        return *max_element(dp.begin(), dp.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.1 最长递增子序列应用

354.俄罗斯套娃

17.08 马戏团人塔

做完上面那俩题之后, 在做这个题, 如果这个题还不会做, 请重复做上面那俩题, 直到不看答案, 能够解决这个题, 算成功

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
1
2
3
4
5
6

思考:
首先想一下, 如果说把这个二维变成一维, 是不是就是最长递增子序列
只不过这个题增加了一个维度, 那我们思考一下, 能不能先对一侧进行排序, 然后在另一侧计算最长递增子序列呢???
答案很显然是可以的

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
先对list的第一列排序, [[2,3], [5,4], [6,4], [6,7]]
然后在对第一列相等的, 倒叙排序第二列 , [[2,3], [5,4], [6,7], [6,4]]
然后在看[3,4,7,4]的最长递增子序列即可
思考: 第一个排序可以理解, 为何倒叙排列第二列???
参考 [[2,3], [5,4], [5,8], [6,7], [6,6], [6,3]]
这里如果[[5,4], [5,8]]是顺序, 则[3,4,8,7] 最长子序列是3, 也就是吧[5,4] 包金来了, 
但是[[6,7], [6,6], [6,3]], [3,4,8,7,6,3], 就不会把[[6,6], [6,3]]包进来;
1
2
3
4
5
6
7
8

class Solution {
public:
    struct myCompare{
        bool operator()(vector<int> &a, vector<int> &b){
            // 先对第一列进行排序, 如果第一列有相等的比如[2,1], [2,3] 在对第二列进行排列成[2,3],[2,1],
            return (a[0] < b[0]) || (a[0]==b[0] && a[1] > b[1]);
        }
    };

    int maxEnvelopes(vector<vector<int>> &nums){
        if(nums.empty()) return 0;
        int n=nums.size();
        sort(nums.begin(), nums.end(), myCompare()); // 按要求排序
        vector<int>dp (n, 1);
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i][1] > nums[j][1]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
        
    }
};
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

3. 路径问题

120.三角形最小路径和

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
1
2
3
4
5
6
7
8

class Solution {
public:
    int minimumTotal(vector<vector<int>>& nums) {
        if(nums.empty() || nums[0].empty()) return 0;

        int m=nums.size(), n=nums[m-1].size();
        // dp[i][j] 表示从[i,j] 到低的最小路径和
        vector<vector<int>> dp(m, vector<int>(n)); 

        // 自底向上计算最小值
        for(int i=0; i<n; i++){
            dp[m-1][i] = nums[m-1][i];
        }

        for(int i=m-2; i>=0; i--){ // 从倒数第二行往上
            for(int j=0; j<=i; j++){ // 从左往右
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + nums[i][j];
            }
        }
        return dp[0][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

64. 最短路径和

给定一个包含非负整数的m x n网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
输入：grid = [[1,2,3],[4,5,6]]
输出：12
1
2
3
4
5

思考:

1. 最短路径和有点像贪婪算法的意思
2. 从左上角开始, 找右/下最小值走, 但是显然不对, 就如上图所示
3. 但是可以想一下, 当前值只跟左/上两个有关系, 所以最终dp[i][j]就可表示为从(0,0)->(i,j)的对小花费

dp[i][j] = min(dp(i-1, j) , dp(i, j-1)) + nums[i][j];
边界条件就是dp的第一列和第一行是nums的累加
1
2

class Solution {
public:
    int minPathSum(vector<vector<int>>& nums) {
        if(nums.empty() || nums[0].empty()) return 0;
        int m = nums.size(), n = nums[0].size();

        vector<vector<int>> dp(m, vector<int>(n));

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0) dp[0][0] = nums[0][0];
                else if(i==0) dp[i][j] = dp[i][j-1]+nums[i][j];
                else if(j==0) dp[i][j] = dp[i-1][j]+nums[i][j];
                else dp[i][j] = min(dp[i-1][j], dp[i][j-1])+nums[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
1
2

1. dp[i][j]表示从i,j到左上的正方形边长

class Solution {
public:
    int min_3(int &a, int &b, int &c){
        return min(min(a, b),c);
    }

    /*
    1. dp[i][j] 表示从(i,j)到 左上方 最大的正方形的边长
    2. dp[i][j] = min(左, 上, 左对角) + 1
    */
    int maximalSquare(vector<vector<char>>& nums) {
        if(nums.empty() || nums[0].empty()) return 0;
        int m=nums.size(), n=nums[0].size();

        int ans=0;
        vector<vector<int>>dp(m, vector<int>(n,0));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || j==0){
                    dp[i][j] = nums[i][j] - '0';
                }
                else if(nums[i][j] == '1'){
                    dp[i][j] = min_3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans*ans;
    }
};
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

4. 背包问题

• 组合优化的 NP 完全问题

• 有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

• 对于背包问题动态方程,

• 设dp[i,j]表示第i物品容量为j的位置背包的价值最多
  因此可以考虑这样求解
  i物品放入背包, 此时背包减去i物品重量后,剩余空间是j-w[i], 所以找到上一个物品的j-w[i]

01背包问题

• 这里需要注意的是: 边界条件
• 跳转关系见图示
  

/*
1. dp含义: dp[i][j] 表示任取0-i的物品放到容量为j的背包里面的最大值
2. 递推公式: dp[i][j]取决于当前物品
             i不放 dp[i][j]=dp[i-1][j] 就跟上一个物品放不放一致
             i放dp[i][j]=dp[i-1][j-weight[i]] + value[i] 空间减掉当前物品空间, 价值加上当前拿物品的价值,
3. 初始化: 第一行和第一列
4. 循环顺序: 
*/
int bakage_01(vector<int> weight, vector<int> value, int maxW){
    vector<vector<int>> dp(weight.size(), vector<int>(maxW+1, 0));
    for(int i=0; i<weight.size(); i++){ //物品
        for(int j=1; j<=maxW; j++){ // 背包容积
            if(i == 0 && weight[0] <= j) { // 第一行, 第一个物品如果重量大于背包容量, 则为value0
                dp[0][j] = value[0];
            }else if(j < weight[i]){ // 背包容积小
                dp[i][j] = dp[i-1][j]; //只跟上一个物品相关
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }
    print_vv(dp);
    return dp[weight.size()-1][maxW];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 空间压缩
  因为上面dp[i]行值只与i-1相关, 所以只需要定义一维空间, 一行一行进行填写, 最后完成dp[j]即为所求

// 空间压缩
int knapsack_optimize(vector<int> weights, vector<int> values, int N, int W) {
	vector<int>dp(W+1, 0);
	int w,v;
	for(int i=1; i<=N; i++){
		w=weights[i-1], v=values[i-1];
		for(int j = W; j>=w; j--){ // 这里大于w是为了去除没用的, 也可以为j>0
			dp[j] = max(dp[j], dp[j-w]+v);
		}
		print_v(dp);
	}
	return dp[W];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

01背包问题的应用 是否可以一个数组分成和相等的两部分

416. 是否可以一个数组分成和相等的两部分

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1
2
3
4
5
6

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false; 
        int target = sum/2;
        if(*max_element(nums.begin(), nums.end()) > target) return false;

        vector<vector<bool>> dp(nums.size(), vector<bool>(target+1, false));
        dp[0][nums[0]] = true; // 第一行的第nums[0]列为true 初始化, 因为一个物品放到背包中正好等于背包容积
        for(int i=1; i<nums.size(); i++){
            for(int j=1; j<=target; j++){
                if(nums[i] > j) dp[i][j] = dp[i-1][j]; // 当前物体容积太大, 不取, 则跟上面的一样
                else if(nums[i] == j) dp[i][j] = true; // 当前值正好等于背包容积
                else{
                    // 当前值小于背包容积, 放进去的话是dp[i-1][j-nums[i]], 不放进去的话是dp[i-1][j]
                    dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j]; 
                }
            }
        }
        return dp[nums.size()-1][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.2 完全背包问题

int knapsack_fully(vector<int> weights, vector<int> values, int N, int W) {
	std::vector<std::vector<int>> dp(N+1, std::vector<int>(W+1, 0));
	int w,v;
	for(int i=1; i<=N; i++){
		w=weights[i-1], v=values[i-1];
		for(int j = 1; j<=W; j++){
			if(j>=w){  
				dp[i][j] = max(dp[i-1][j], v+dp[i][j-w]);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	print_vv(dp);
	return dp[N][W];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

416. 是否可以一个数组分成和相等的两部分

• Input: [1,5,11,5]
• Output: true
• 仔细一看, 本题不就是一道01背包问题么
• 将所有值相加对半, 等于11
• 也就是背包最大值为11, input是物品的重量, 价值不用考虑
  

/**
 * @Author   zjq
 * @DateTime 2021-02-08
 * @技巧 与01背包问题相似, 都是小问题到大问题, 比如先判断前i个数, 是否能和为nums/2
 * @function
 * @param    nums       数列
 * @return              是否能分成两个数列, 使得两数列之和相等
 */
bool canPartition(vector<int> nums) {
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2) return false;
	int target = sum / 2, n = nums.size();
	vector<vector<bool>> dp(n+1, vector<bool>(target + 1, false));
	for (int i = 0; i <= n; ++i) {
		dp[i][0] = true;
	}
	print_vv(dp);
	for (int i = 1; i <= n; ++i) {
		for (int j = nums[i-1]; j <= target; ++j) {
			dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
		}
		print_vv(dp);
	}
	return dp[n][target];
}

bool canPartition_optimize(vector<int> nums) {
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2) return false;
	int target = sum / 2;
	vector<vector<bool>> dp(nums.size(), vector<bool>(target + 1, false));
	dp[0][nums[0]] = true; //设置第一边界条件
	for (int i = 1; i < nums.size(); ++i) {
		for (int j = 0; j <= target; ++j) {
			if(nums[i] == j) {   //选择当前值, 正好等于 直接设置为1
				dp[i][j]==true;
			}else if(nums[i]<j){ // 选择当前值, 小于
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
			}else{
				dp[i][j] = dp[i-1][j]; // 首先默认不加入当前值nums[i]
			}
		}
		if(dp[i][target]) return true; // 没行结束判定一下最后一个值, target已经实现, 就不用在继续循环了
	}
	print_vv(dp);
	return dp[nums.size()-1][target];
}

bool canPartition_optimize2(vector<int> nums) {
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2) return false;
	int target = sum / 2;
	vector<vector<bool>> dp(nums.size(), vector<bool>(target + 1, false));
	dp[0][0] = true; // 边界条件
	dp[0][nums[0]] = true; //设置第一边界条件
	for (int i = 1; i < nums.size(); ++i) {
		for (int j = 0; j <= target; ++j) {
			dp[i][j] = dp[i-1][j]; // 首先默认不加入当前值nums[i]
			if(nums[i]<=j){ // 选择当前值, 小于
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
			}
		}
		// if(dp[i][target]) return true;
	}
	print_vv(dp);
	return dp[nums.size()-1][target];
}

vector<int> list={1,5,11,5};
canPartition(list);
// canPartition_optimize2(list);
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

5. 分割问题

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
1
2
3
4
5
6
7

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<vector<long long>> f(n + 1, vector<long long>(m + 1, LLONG_MAX));
        vector<long long> sub(n + 1, 0);
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, m); j++) {
                for (int k = 0; k < i; k++) {
                    f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return (int)f[n][m];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

class Solution {
public:
    int numSquares(int n) {
        if(n < 1) return 0;
        vector<int> dp(n+1, n);
        dp[0] = 0, dp[1] = 1;
        for(int i=1; i<=n; i++){
            for(int j=1; j*j<=i; j++){
                dp[i] = min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6. 递进问题(类似斐波那契数列)

解题思路:

1. 先根据问题画树形图
2. 由树形图推出前后关系
3. 在确定初始dp

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

class Solution {
public:
int coinChange(vector<int>& nums, int target) {
    if(target==0)  return 0;
    if(nums.empty() || *min_element(nums.begin(), nums.end()) > target) return -1;
    vector<int> dp(target+1, target+1); // 默认都是最大
    sort(nums.begin(), nums.end());

    for(int &a : nums){
        if(a > target) nums.pop_back();
    }
    int n = nums.size();
    // print_v(nums);
    // 先把每个需要一个硬币就搞定的安排上
    for(int &a: nums) dp[a] = 1; 

    // 把前面的都给赋值为0
    for(int i=0; i<nums[0]; i++) dp[i] = 0;
    
    // 从第一个硬币下一个位置开始
    for(int i=nums[0]+1; i<=target; i++){
        for(int j=0; j<n; j++){
            // 当前位置减去一个硬币还有空闲, 并且这个空闲有硬币可以弥补
            int a = i-nums[j];
            if((a >= 0) && (dp[a] != target+1) &&  (dp[a] != 0)) {
                dp[i] = min(dp[a]+1, dp[i]);
            }
        }
    }
    return dp[target]==target+1 ? -1 : dp[target];
}
};
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

53. 最大子序和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
3

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;

        int n=nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];

        for(int i=1; i<n; i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

413. 等差数列划分

/*
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
*/

class Solution {
public:
    /*
        等差数列的要求是nums[i]-nums[i-1] == nums[i-1]-nums[i-2] 
        因此当前值跟前两个值有关系, 因此与斐波那契一样,  只需要定义前两个值即可
    */
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n=nums.size();
        vector<int> dp(n, 0); // dp[i] 表示从0-i总共多少个等差数列
        for(int i=2; i<n; i++){
            if(nums[i]-nums[i-1] == nums[i-1]-nums[i-2]){
                dp[i] = dp[i-1] + 1;
            }
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

华为笔试题: 外卖员到达目标楼层的最短消费时间

/*
题目:
    外卖员小w, 每天在大厦运送外卖, 大厦共L层, 
    当小W处于第N层, 
    每分钟通过步行上楼到达N+1, 或下楼到达N-1, 或者电梯到达2N
    给定小w所处位置N, 目的楼层M, 计算小w送达的最短时间

分析:
    首先选择动态规划解题, dp[i] 表示从小王位置到达i点的时间
    小王能走得路子只有 +1, -1, *2
    因此 当目标值在楼下, 只能-1
    当目标值在楼上分两种情况考虑: +1往上, 或者楼下*2, 两者的最小值
*/
int stairs(int location, int target){
    // 如果当前位置在目前位置以下, 只能向下走
    if(target<=location) return location-target; 

    vector<int> dp(target+1, 0);

    // 当目的地在小王脚下时, 直接赋值
    for(int i=1; i<location; i++){
        dp[i] = location-i;
    }

    // 当目的地在小王头上时, 分类讨论
    for(int i=location+1; i<=target; i++){
        int down = 1+dp[i-1]; // 向上走一步的长度
        // 比如小王9楼, 当前所求是10楼,  可以是5楼*2
        // 比如当前所求是11楼, 则可以是5楼*2+1, 也就是后面的+2
        int el = i%2==0 ? dp[i/2]+1 : 2+dp[(i+1)/2]; 
        dp[i] = min(down, el); // 是直接上走得, 还是从下面*2上走的
    }
    return dp[target];
}

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

7. 两次dp 夹击解题

542. 每个位置到0的距离

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

解题思路:

1. 首先设置二维数组, dp[i][j] 表示位置i,j与0最近的距离
2. 默认dp填充最大值(这里可以设置成二维矩阵的对交线长度)
3. 因为需要一步步查找当前位置与0的距离
4. 所以从上往下, 从左往右开始, 当遇到0时, 直接置零, 当遇到1时, 直接上和左的值加一与当前值进行比大小
5. 然后从下往上, 从右往左, 与上面同理

# nums
1 0 1 0 0 
1 0 1 0 1 
0 1 0 0 0 
0 0 1 1 1 
1 0 1 0 0 
# 从上往下, 从左往右
10000 0 1 0 0 
10000 0 1 0 1 
0 1 0 0 0 
0 0 1 1 1 
1 0 1 0 0 
# 从下往上, 从右往左
1 0 1 0 0 
1 0 1 0 1 
0 1 0 0 0 
0 0 1 1 1 
1 0 1 0 0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& nums) {
        if(nums.empty() || nums[0].empty()) return {};
        int m=nums.size(), n=nums[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 10000)); // 因为n<=10^4
        // 先从左往右, 从上往下, 这样就可以确定一半位置
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(nums[i][j] == 0) dp[i][j] = 0;
                else{
                    if(i > 0) dp[i][j] = min(dp[i][j], dp[i-1][j]+1); // 上→下
                    if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j-1]+1); // 左→右
                }
            }
        }

        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                if(nums[i][j] == 0) {}
                else{
                    if(i < m-1) dp[i][j] = min(dp[i][j], dp[i+1][j]+1); // 上→下
                    if(j < n-1) dp[i][j] = min(dp[i][j], dp[i][j+1]+1); // 左→右
                }
            }
        }
        return 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
29

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

解题思路:

• 从左向右遍历得到左侧最大值
• 从右向左遍历得到右侧最大值
• 两个最大值减去当前值就是积水
  

int trap(vector<int> &height){
    int ans = 0;
    int n = height.size();
    if(n<3) return 0; // 低于三个柱子不可能积水

    // 从左往右遍历得到左侧最大值
    vector<int> left_max_arr(n); 
    left_max_arr[0] = height[0];
    for(int i=1; i<n; i++){
        left_max_arr[i] = max(left_max_arr[i-1], height[i]);
    }

    // 从右往左遍历得到右侧最大值
    vector<int> right_max_arr(n); 
    right_max_arr[n-1] = height[n-1];
    for(int i=n-2; i>=0; i--){
        right_max_arr[i] = max(right_max_arr[i+1], height[i]);
    }

    // 合并求解
    for(int i=0; i<n; i++){
        ans += min(left_max_arr[i], right_max_arr[i]) - height[i];
    }
    return ans;
}
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