Steven's BlogAppearance
每天一道Rust-LeetCode(2020-01-17)
坚持每天一道题,刷题学习Rust.
题目描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 示例 2:
输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。 在真实的面试中遇到
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
有一点肯定是真的: 我整体的最好收益取决于历史收益+未来收益 在当前状态: 我的最好收益不外乎两种情况,持有股票或者不持有股票两种情况 那么明天我的状态就是基于这两种情况向前继续滚动 交易次数不限制,那就不用关心买卖次数 dp[i][k][state] state:0 表示持有股票,1表示不持有股票 dp里面存储的是这个状态对应的利润 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-2/
dp[i][k][0] 表示还剩下k次交易,不持有股票的利润 dp[i][k][1] 表示还剩下k次交易,持有股票的利润
解题过程
rust
struct Solution {}
use std::cmp::max;
impl Solution {
//内存占用超限
pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
if k == 0 || prices.len() == 0 {
return 0;
}
let mut k = k as usize;
if k >= prices.len() / 2 + 1 {
//这可以优化成不限制次数,退化成了O(N)
k = prices.len() / 2 + 1; //最多进行prices.len()/2次交易,不可能进行更多了,一买一卖
}
let mut dp = vec![vec![vec![0; 2]; k as usize]; prices.len()];
println!("k={},priceslen={}", k, prices.len());
for i in 0..k {
dp[0][i][1] = -prices[0]; //剩下k-1次交易,持有股票 ,
}
// println!("dp0={:?}", dp[0]);
for i in 1..prices.len() {
let price = prices[i];
for j in 0..k as usize {
//剩下j次交易,不持有股票,
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + price);
let mut last = 0;
if j < k - 1 {
last = dp[i - 1][j + 1][0];
}
//剩下j次交易,持有股票
dp[i][j][1] = max(dp[i - 1][j][1], last - price);
}
println!("i={}", i);
// println!("dp[{}]={:?}", i, dp[i]);
}
let l = prices.len();
dp[l - 1][0][0]
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test() {
// [3,2,6,5,0,3], k = 2
assert_eq!(Solution::max_profit(2, vec![3, 2, 6, 5, 0, 3, 2, 3]), 7);
}
}
一点感悟
状态机的方式,思路清晰了很多.当然结果不优化,很容易改进.
其他
欢迎关注我的github,本项目文章所有代码都可以找到.