剪绳子
把一根绳子剪成多段，并且使得每段的长度乘积最大。
- 优-动态规划
- 现有一个数组，用来存储每一个长度下，最优的乘积值。
- 前四个没什么好说的，第五个开始，就是依次遍历“第一次减的长度”，然后乘上之前存储的最优值，在这个遍历中，找到最大的那个答案。
- “第一次减的长度”从1开始到其本身-1。
import java.util.*;
public class Solution {
public int cutRope(int target) {
//不超过3直接计算
if(target <= 3)
return target- 1;
//dp[i]表示长度为i的绳子可以被剪出来的最大乘积
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
//遍历后续每一个长度
for(int i = 5; i <= target; i++)
//可以被分成两份
for(int j = 1; j < i; j++)
//取最大值
dp[i] = Math.max(dp[i], j * dp[i - j]);
return dp[target];
}
}
- 贪心
- 代码没有难度，主要是思考的过程。
- 最后得出的结论是，分成3最好，如果有1的出现，将一个3与其平摊，变成两个2。
- 思考的逻辑是，从1开始的最优情况，从2开始的最优情况....发现前4个固定，后面开始多分3。
- 将绳子拆成 1 和 n-1，则 1(n-1)-n=-1<0
- 将绳子拆成 1 和 n-1，则 1(n-1)-n=-1<0
- 将绳子拆成 3 和 n-3，则 3(n-3)-n = 2n-9
- 将绳子拆成 4 和 n-4，因为 4=2*2，效果和拆成 2 一样。
- 将绳子拆成 5 和 n-5，因为 5=2+3，尽可能拆成 2 和 3。
- 将绳子拆成 6 和 n-6，因为 6=3+3，拆成 3 和 3。
- https://github.com/CyC2018/CS-Notes/blob/master/notes/14.%20%E5%89%AA%E7%BB%B3%E5%AD%90.md
public class Solution {
public int cutRope(int target) {
//不超过3直接计算
if(target <= 3)
return target - 1;
int res = 1;
while(target > 4){
//连续乘3
res *= 3;
target -= 3;
}
return res * target;
}
}
股票的最大利润
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
给你一个数组，这个数组代表股票每天的价格，你要选一天买入股票，然后再选另外一天卖出股票，并使你的利润最大。返回一个最大的利润值，如果无法盈利，返回0
- 贪心
- 每次卖出都是有可能最好的结果，那有没有更好的可能，在遍历的时候，再计算。
- 问题转变为，怎么买卖是最合适的。
- 买入的那个值是最小的，且往后的计算的过程中，差值比之前计算的结果要大。
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int soFarMin = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
soFarMin = Math.min(soFarMin, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
}
return maxProfit;
}
