(六)动态规划【C++刷题】
2021/12/23 11:07:05
本文主要是介绍(六)动态规划【C++刷题】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
圆环回原点问题
1.问题描述
一个环,有n个点,编号从0增加,从原点0出发,每次只能走一步,每步可以顺时针到下一个点,也可以逆时针到上一个点,经过k步回到原点有多少种方法?
2.输入输出
- Input:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], k=1/2
- Output:0/2
3.算法分析
*【动态规划】回到0点可以从右面回来,也可以从左面回来,有多少种方法。
- dp[k][j]表示从j点走k步到达原点0的方法树,转化为相邻的点经过k-1步回到原点的问题:
4.编程实现
#include <iostream> #include <vector> using namespace std; class Solution { public: int getStepNum(vector<int> &nums, int k) { int n = nums.size(); int dp[k+1][n]; // dp[i][j]表示经过i步到达k点的方法数 dp[0][0] = 1; // 经过0步到达0点的方法数为1 for (int i = 1; i < n; i++) { dp[0][i] = 0; } for (int i = 1; i <= k; i++) { for (int j = 0; j < n; j++) { dp[i][j] = dp[i-1][(j+1) % n] + dp[i-1][(j-1+n) % n]; } } return dp[k][0]; } }; int main() { vector<int> nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int k = 2; Solution sol; cout << sol.getStepNum(nums, k); }
接雨水
leetcode:https://leetcode-cn.com/problems/trapping-rain-water/
Nowcoder:https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=188
1.问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
2.输入输出
- Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]
- Output:6
3.算法分析
【解法一:动态规划】对于下标i,下雨后水能到达的最大高度等于下标i两边的最大高度的最小值,下标i处能接到的雨水量等于下标i处的水能到达的最大高度减去height[i]。
思路:从左向右扫描得到每个height获得到左边最大高度,从右到左扫描得到每个height获得右边最大高度,最后遍历一遍每个下标位置即可得到能接的雨水总量。即两个dp数组。
- 时间复杂度:\(O(n)\)
- 空间复杂度:\(O(n)\)
【解法二:单调栈】维护一个单调栈,单调栈存储的是下标,满足从栈底到栈顶的下标对应的数组height中的元素递减。
(1)从左到右遍历数组,遍历到下标i时,如果栈内至少有两个元素,记栈顶元素为top,top的下面一个元素是left,则一定有height[left]≥height[top]。如果height[i]>height[top],则得到一个可以接雨水的区域,该区域的宽度是i-left-1,高度是min(height[left], height[i]-height[top]),根据宽度和高度计算得到该区域能接的雨水量。
(2)为了得到left,需要将top出栈。对top计算能接的雨水量之后,left变成新的top,重复上述操作,直到栈为空,或者栈顶下标对应的hegiht中的元素大于或等于height[i]。
(3)在对下标i处计算能接的雨水量之后,将i入栈,继续遍历后面的下标,计算能接的雨水量。遍历结束后得到能接的雨水量。
- 时间复杂度:\(O(n)\)
- 空间复杂度:\(O(n)\)
【解法三:双指针】动态规划中,将leftMax和rightMax最小值决定,从左往右和从右往左,用双指针和两个变量代替两个数组。
- 时间复杂度:O(n)
- 空间复杂度:O(1)
4.编程实现
// #include <bits/stdio.h> #include <iostream> #include <vector> #include <stack> using namespace std; class Solution { public: int trap1(vector<int> &heights) { // 动态规划法 int n = heights.size(); if (n == 0) return 0; vector<int> leftMax(n, 0); leftMax[0] = heights[0]; for (int i = 1; i < n; i++) { leftMax[i] = max(leftMax[i-1], heights[i]); } vector<int> rightMax(n, 0); rightMax[n-1] = heights[n-1]; for (int i = n-2; i >= 0; i--) { rightMax[i] = max(rightMax[i+1], heights[i]); } int ans = 0; for (int i = 0; i < n; i++) { ans += min(leftMax[i], rightMax[i]) - heights[i]; } return ans; } int trap2(vector<int> &heights) { // 单调栈法 int n = heights.size(), ans = 0; stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && heights[i] > heights[stk.top()]) { int top = stk.top(); stk.pop(); if (stk.empty()) break; int left = stk.top(); int currWidth = i - left - 1; int currHeight = min(heights[left], heights[i]) - heights[top]; ans += currWidth * currHeight; } stk.push(i); } return ans; } int trap3(vector<int> &heights) { // 双指针——dp空间压缩法 int ans = 0, left = 0, right = heights.size() - 1; int leftMax = 0, rightMax = 0; while (left < right) { leftMax = max(leftMax, heights[left]); rightMax = max(rightMax, heights[right]); if (heights[left] < heights[right]) { ans += leftMax - heights[left]; ++left; } else { ans += rightMax - heights[right]; --right; } } return ans; } }; int main() { vector<int> heights; int val; Solution sol; getchar(); while (cin >> val) { heights.push_back(val); if (cin.get() == ']') break; } cout << sol.trap3(heights) << endl; return 0; }
最大子序和
Leetcode:https://leetcode-cn.com/problems/maximum-subarray/)
1.问题描述
给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
2.输入输出
Input:nums=[-2, -1, -3, 4, -1, 2, 1, -5, 4]
Output:6
3.算法分析
(1)划分子问题:每个数字都可以选择加入前一位的序列或者当前序列重新开始求和。
(2)定义子问题:定义一维数组dp[n],结果定义sum
(3)确定边界:dp[0] = nums[0]。
(4)状态转移方程确定:dp[i]=max(dp[i-1]+nums[i], nums[i]),sum为max(sum, dp[i])
4.编程实现
#include <iostream> #include <string> #include <vector> using namespace std; class Solution{ public: int maxSubArray(vector<int> & nums) { int n = nums.size(); if (n == 1) return nums[0]; int pre = 0, sum = nums[0]; for (int i = 0; i < n; i++) { pre = max(pre+nums[i], nums[i]); sum = max(sum, pre); } return sum; } }; int main() { int get; Solution sol; vector<int> nums; getchar(); while (cin >> get) { nums.push_back(get); if (cin.get() == ']') break; } cout << sol.maxSubArray(nums) << endl; return 0; }
这篇关于(六)动态规划【C++刷题】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享