(六)动态规划【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步回到原点的问题:

\[dp[k][j]=dp[k-1][j+1]+dp[k-1][j-1] \\ 【注:j-1和j+1会超出0至n-1范围】,因而转化为下式:\\ dp[k][j]=dp[k-1][(j-1+n)\%n]+dp[k-1][(j+1)\%n] \]

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++刷题】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程