188. 买卖股票的最佳时机 IV

每天一道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次交易,持有股票的利润

解题过程

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,本项目文章所有代码都可以找到.

xxxxxxxsgg dsgggg 本站总访问量 本站访客数人次