@ 代码随想录算法训练营第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

相关文章

Java使用Javassist动态生成HelloWorld类

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

Redis实现高效内存管理的示例代码

《Redis实现高效内存管理的示例代码》Redis内存管理是其核心功能之一,为了高效地利用内存,Redis采用了多种技术和策略,如优化的数据结构、内存分配策略、内存回收、数据压缩等,下面就来详细的介绍... 目录1. 内存分配策略jemalloc 的使用2. 数据压缩和编码ziplist示例代码3. 优化的

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python

GO语言短变量声明的实现示例

《GO语言短变量声明的实现示例》在Go语言中,短变量声明是一种简洁的变量声明方式,使用:=运算符,可以自动推断变量类型,下面就来具体介绍一下如何使用,感兴趣的可以了解一下... 目录基本语法功能特点与var的区别适用场景注意事项基本语法variableName := value功能特点1、自动类型推

GO语言中函数命名返回值的使用

《GO语言中函数命名返回值的使用》在Go语言中,函数可以为其返回值指定名称,这被称为命名返回值或命名返回参数,这种特性可以使代码更清晰,特别是在返回多个值时,感兴趣的可以了解一下... 目录基本语法函数命名返回特点代码示例命名特点基本语法func functionName(parameters) (nam

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中,我们经常需要从 W

使用Spring Cache本地缓存示例代码

《使用SpringCache本地缓存示例代码》缓存是提高应用程序性能的重要手段,通过将频繁访问的数据存储在内存中,可以减少数据库访问次数,从而加速数据读取,:本文主要介绍使用SpringCac... 目录一、Spring Cache简介核心特点:二、基础配置1. 添加依赖2. 启用缓存3. 缓存配置方案方案

MySQL的配置文件详解及实例代码

《MySQL的配置文件详解及实例代码》MySQL的配置文件是服务器运行的重要组成部分,用于设置服务器操作的各种参数,下面:本文主要介绍MySQL配置文件的相关资料,文中通过代码介绍的非常详细,需要... 目录前言一、配置文件结构1.[mysqld]2.[client]3.[mysql]4.[mysqldum

Python多线程实现大文件快速下载的代码实现

《Python多线程实现大文件快速下载的代码实现》在互联网时代,文件下载是日常操作之一,尤其是大文件,然而,网络条件不稳定或带宽有限时,下载速度会变得很慢,本文将介绍如何使用Python实现多线程下载... 目录引言一、多线程下载原理二、python实现多线程下载代码说明:三、实战案例四、注意事项五、总结引

Go语言连接MySQL数据库执行基本的增删改查

《Go语言连接MySQL数据库执行基本的增删改查》在后端开发中,MySQL是最常用的关系型数据库之一,本文主要为大家详细介绍了如何使用Go连接MySQL数据库并执行基本的增删改查吧... 目录Go语言连接mysql数据库准备工作安装 MySQL 驱动代码实现运行结果注意事项Go语言执行基本的增删改查准备工作