day41.动态规划

本文主要是介绍day41.动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.动态规划

121.买卖股票的最佳时机I

思路:dp[i][1] 表示第i天不持有股票所得最多现金  dp[i][0] 表示第i天持有股票所得最多现金

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

122.买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 思路1:贪心做法，局部最优推出全局最优。

class Solution {
public:int maxProfit(vector<int>& prices) {int money=0;for(int i=1;i<prices.size();i++){if(prices[i]-prices[i-1]>0){money+=prices[i]-prices[i-1];}}return money;}
};

 动态规划做法:

dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金

class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();vector<vector<int>> dp(len,vector<int>(2,0));dp[0][0]-=prices[0]; //0 代表持有股票所得的资金 = 前一天的股票资金-今天的股票资金dp[0][1]=0;          //1 第i天不持有股票所得最多现金for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);//如果昨天持有股票 看看卖合适还是不卖合适dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[len-1][1];}
};

二.数据库

1280.学生参加各科的测试次数题目链接

查询出每个学生参加每一门科目测试的次数，结果按 student_id 和 subject_name 排序。

查询结构格式如下所示。

 思路:

select s.student_id,
s.student_name,
su.subject_name,
count(e.subject_name) as attended_exams
from Students as s
joinSubjects as su
left join Examinations as e
on e.student_id=s.student_id
AND e.subject_name=su.subject_name
group by s.student_id,su.subject_name
order by s.student_id,su.subject_name

 子查询:

1327.列出指定时间段内所有下单的产品

写一个解决方案，要求获取在 2020 年 2 月份下单的数量不少于 100 的产品的名字和数目。

返回结果表单的 顺序无要求 。

查询结果的格式如下。

 思路:

select product_name,sum(unit) unit from Products 
join Orders using(product_id)where 
order_date >='2020-02-01' and
order_date <'2020-03-00'
group by product_name 
having unit>=100

1978.上级经理已离职的公司员工

查找这些员工的id，他们的薪水严格少于$30000 并且他们的上级经理已离职。当一个经理离开公司时，他们的信息需要从员工表中删除掉，但是表中的员工的manager_id  这一列还是设置的离职经理的id 。

返回的结果按照employee_id 从小到大排序。

查询结果如下所示：

 

 思路:

select employee_id
from Employees 
where salary < 30000 and
manager_id not in (select employee_id from Employees)
order by employee_id

这篇关于day41.动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---