当前位置:   article > 正文

C++ 吃透动态规划算法

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.最长公共子序列

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/672447
推荐阅读
相关标签
  

闽ICP备14008679号