程序地带

数据结构与算法---动态规划---礼物的最大价值、买卖股票的最佳时期


礼物的最大价值

47. 礼物的最大价值


在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?


示例 1: 输入:


[
[1,3,1],
[1,5,1],
[4,2,1]
]

输出: 12


解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物


提示: 0 < grid.length <= 200 0 < grid[0].length <= 200


思路

暴力法 贪心法 回溯法 动态规划


DP

使用DP,就是几个步骤: 是不是最值问题、能不能使用DP(原问题能否分解为子问题、有无后效性)、使用DP的步骤(确定dp含义、确定边界值、状态转移方程)


是不是最值问题?


能否使用DP
原问题能否分解为子问题 由于只能向下或者向右,对于dp[i][j]可以由dp[i - 1][j]和dp[i][j - 1]取比较大的再加上自身价值确定有无后效性 无
DP步骤

确定dp含义 dp[i][j] 表示,第i行,第j列的最大价值

确定边界值 dp[0][0] = valuesArray[0][0] dp[0][j] = dp[0][j - 1] + valuesArray[0][j]; dp[i][0] = dp[i - 1][0] + valuesArray[i][0];

确定转移方程 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + valuesArray[i][j];


了解以上,不难写出代码:


class Solution {
public int maxValue(int[][] grid) {
if(grid == null) return 0;
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for(int j = 1; j < col; j++){
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for(int i = 1; i < row; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int j = 1; j < col; j++){
for(int i = 1; i < row; i++){
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
}

注意二维数组的行列 两层for循环,row和col谁在外都可以


拓展题

将dp[][]二维数组,优化为dp[]一维数组


买卖股票的最佳时期

121. 买卖股票的最佳时期


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


如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。


注意:你不能在买入股票前卖出股票。


示例 1:


输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。


示例 2:


输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


思路

第一眼看到题目还以为是数学模型,可以预测下股票的买卖时机,正好自己学习下。 不曾想,这道题是事后诸葛亮,对炒股没一点用。我要是提前知道哪天最高价,那我不发了。。。。。。


最大利润,就是在低点买,在高点卖。并且,低点时机在高点时机前


暴力法

求出所有的利润,两个for循环搞定


class Solution {
public int maxProfit(int[] prices) {
//至少两个值
if(prices == null || prices.length == 0 || prices.length == 1) return 0;
int max = 0;
for(int i = 0; i<prices.length; i++){
for(int j = i + 1; j<prices.length; j++){
max = Math.max(prices[j] - prices[i], max);
}
}
return max;
}
}
贪心

倒推一下,不先考虑在哪一天买,考虑在哪一天卖 假如在dp[i]卖,那么,需要在[0, i)里面,选择一个最小值,这样dp[i]的价值最大


在这里插入图片描述


class Solution {
public int maxProfit(int[] prices) {
//至少两个值
if(prices == null || prices.length == 0 || prices.length == 1) return 0;
//前面扫描过的最小价格
int minPrice = prices[0];
int maxValue = 0;
for(int i = 1; i<prices.length; i++){
minPrice = Math.min(prices[i], minPrice);
if(prices[i] > minPrice){
maxValue = Math.max(prices[i] - minPrice, maxValue);
}
}
return maxValue;
}
}

算动态规划吗? 好像,不算,没有状态转移方程


DP

第i天买,第j天卖的利润等于: 第i-j天内,所有相邻两天股价差的和 例如:


0 1 2 3 4 5
7 1 5 3 6 4

第1天到第4天的利润等于: 第4天价格-第3天价格 = 6 - 3 = 3 第3天价格-第2天价格 = 3 - 5 = -2 第2天价格-第1天价格 = 5 - 1 = 4


加起来,和为:5,因此,第4天卖、第1天买的利润为5


在这里插入图片描述


最后,题目被转化为求最大子数组和 或者 最大连续子序列和的问题


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/IOSSHAN/article/details/109757165

随机推荐

STM32串口仿真/发送数据

利用已经建立的工程模板,在KeilforARMV5中编写代码,实现如下功能:配置串口1,使得串口循环输出自己的学号(以字符串形式&...

保证遵循规章制度 阅读(205)

统计基础(五)假设检验中的检验方法

TestingforMeans1.R语言的统计分布函数2.如何制定决策规则2.1假设检验与置信区间的关系2.2假设检验的步骤3.独立总体&相关总体3.1两个平均数之间的差值4.检验方法4.1z检验4....

H.Wingjan 阅读(221)

2020-11-19

Spring的下载地址下载地址:https://repo.spring.io/release/org/springframework/spring/选择相应版本进行下载:然...

出其东门&往 阅读(469)

定义一个json数组并赋值_JSON学习笔记

什么是JSONjson是一种与开发语言无关的、轻量级的数据格式。全称JavaScriptObjectNotation.优点易于人的阅读和编写,易于程序解析与生产样例标准的JSON数据表示...

weixin_39669701 阅读(365)

Ubuntu系统配置RealSense SDK

去github下载插件,下载地址Registertheserver’spublickey:sudoapt-keyadv--keyserverkeys.gnupg.net--recv-ke...

_Karry 阅读(943)

第十七章 IO流

目录17.1IO流的概念17.2基本分类17.3体系结构17.4相关流的详解17.4.1FileWriter类(重点)17.4.2FileReader类(重点...

下雨天看彩虹 阅读(385)

客户要求提供源码_直播网站源码开发时的几点误区

但凡程序软件,都有源码,对于直播软件亦是如此。通过成品的直播网站源码可以快速实现直播平台开发搭建,是目前很受欢迎的一种直播软件开发方式。科很多投资商对直播网站...

weixin_39528219 阅读(383)