算法-贪心思想
庭前看玉树,肠断忆连枝
一、剪绳子
1、题目描述
把一根绳子剪成多段,并且使得每段的长度乘积最大。
2、解题思路
尽可能得多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。以下为证明过程。
将绳子拆成 1 和 n-1,则 1(n-1)-n=-1
将绳子拆成 2 和 n-2,则 2(n-2)-n = n-4,在 n>=4 时这样拆开能得到的乘积会比不拆更大。
将绳子拆成 3 和 n-3,则 3(n-3)-n = 2n-9,在 n>=5 时效果更好。
将绳子拆成 4 和 n-4,因为 4=2*2,因此效果和拆成 2 一样。
将绳子拆成 5 和 n-5,因为 5=2+3,而 5
将绳子拆成 6 和 n-6,因为 6=3+3,而 6
继续拆成更大的绳子可以发现都比拆成 2 和 3 的效果更差,因此我们只考虑将绳子拆成 2 和 3,并且优先拆成 3,当拆到绳子长度 n 等于 4 时,也就是出现 3+1,此时只能拆成 2+2。
二、股票的最大利润
1、题目描述
可以有一次买入和一次卖出,买入必须在前。求最大收益。
2、解题思路
使用贪心策略,假设第 i 轮进行卖出操作,买入操作价格应该在 i 之前并且价格最低。因此在遍历数组时记录当前最低的买入价格,并且尝试将每个位置都作为卖出价格,取收益最大的即可。
庭前看玉树
肠断忆连枝
Original: https://www.cnblogs.com/taojietaoge/p/15030319.html
Author: 涛姐涛哥
Title: 算法-贪心思想
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/612971/
转载文章受原作者版权保护。转载请注明原作者出处!