@ 代码随想录算法训练营第8周(C语言)|Day54(动态规划)

2024-02-20 23:12

本文主要是介绍@ 代码随想录算法训练营第8周(C语言)|Day54(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

@ 代码随想录算法训练营第8周(C语言)|Day54(动态规划)

Day53、动态规划(包含题目 ● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV )

123.买卖股票的最佳时机III

题目描述

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

题目解答

int maxProfit(int* prices, int pricesSize) {int **dp=(int**)malloc(sizeof(int*)*4);for(int i=0;i<4;i++){dp[i]=(int*)malloc(sizeof(int)*pricesSize);}dp[0][0]=-prices[0];//第一次持有dp[1][0]=0;//第一次不持有dp[2][0]=-prices[0];//第二次持有dp[3][0]=0;for(int i=1;i<pricesSize;i++){dp[0][i]=fmax(dp[0][i-1],-prices[i]);dp[1][i]=fmax(dp[1][i-1],dp[0][i-1]+prices[i]);dp[2][i]=fmax(dp[2][i-1],dp[1][i-1]-prices[i]);dp[3][i]=fmax(dp[3][i-1],dp[2][i-1]+prices[i]);}return dp[3][pricesSize-1];
}

题目总结

买两次的股票问题。

188.买卖股票的最佳时机IV

题目描述

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

题目解答

int maxProfit(int k, int* prices, int pricesSize) {int **dp=(int**)malloc(sizeof(int*)*(2*k+1));for(int i=0;i<(2*k+1);i++){dp[i]=(int*)malloc(sizeof(int)*pricesSize);}for(int i=0;i<pricesSize;i++){dp[0][i]=0;}for(int i=1;i<=k;i++){dp[2*i][0]=0;}for(int i=0;i<k;i++){dp[2*i+1][0]=-prices[0];}for(int i=1;i<pricesSize;i++){for(int z=1;z<(2*k+1);z+=2){dp[z][i]=fmax(dp[z][i-1],dp[z+1][i-1]-prices[i]);dp[z+1][i]=fmax(dp[z+1][i-1],dp[z][i-1]+prices[i]);}}return dp[2*k][pricesSize-1];}

题目总结

从2次过度到无数次。

这篇关于@ 代码随想录算法训练营第8周(C语言)|Day54(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/729835

相关文章

MySQL批量替换数据库字符集的实用方法(附详细代码)

《MySQL批量替换数据库字符集的实用方法(附详细代码)》当需要修改数据库编码和字符集时,通常需要对其下属的所有表及表中所有字段进行修改,下面:本文主要介绍MySQL批量替换数据库字符集的实用方法... 目录前言为什么要批量修改字符集?整体脚本脚本逻辑解析1. 设置目标参数2. 生成修改表默认字符集的语句3

基于Go语言开发一个 IP 归属地查询接口工具

《基于Go语言开发一个IP归属地查询接口工具》在日常开发中,IP地址归属地查询是一个常见需求,本文将带大家使用Go语言快速开发一个IP归属地查询接口服务,有需要的小伙伴可以了解下... 目录功能目标技术栈项目结构核心代码(main.go)使用方法扩展功能总结在日常开发中,IP 地址归属地查询是一个常见需求:

C#使用SendMessage实现进程间通信的示例代码

《C#使用SendMessage实现进程间通信的示例代码》在软件开发中,进程间通信(IPC)是关键技术之一,C#通过调用WindowsAPI的SendMessage函数实现这一功能,本文将通过实例介绍... 目录第一章:SendMessage的底层原理揭秘第二章:构建跨进程通信桥梁2.1 定义通信协议2.2

JAVA实现亿级千万级数据顺序导出的示例代码

《JAVA实现亿级千万级数据顺序导出的示例代码》本文主要介绍了JAVA实现亿级千万级数据顺序导出的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 前提:主要考虑控制内存占用空间,避免出现同时导出,导致主程序OOM问题。实现思路:A.启用线程池

在.NET项目中嵌入Python代码的实践指南

《在.NET项目中嵌入Python代码的实践指南》在现代开发中,.NET与Python的协作需求日益增长,从机器学习模型集成到科学计算,从脚本自动化到数据分析,然而,传统的解决方案(如HTTPAPI或... 目录一、CSnakes vs python.NET:为何选择 CSnakes?二、环境准备:从 Py

Nginx实现端口映射的示例代码

《Nginx实现端口映射的示例代码》本文主要介绍了Nginx实现端口映射的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1. 找到nginx的部署路径2. 备份原来的配置文件3. 编辑nginx.conf文件4. 在

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot?二、环境准备与部署2.1 安装 RustF

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC