阿祁的部落格

LeetCode 188 - Best Time to Buy and Sell Stock IV 解題心得( 題目 )

解題概念:DP、Aliens 優化

解題方法:這題不難，原因是他n、k很小，我們可以假設兩個陣列:

解法(1):二維DP，時間複雜度:O(nk)

dp0[i][j]代表目前不持有，討論時間點i之前進行最多j交易的最佳解。

dp1[i][j]則代表目前持有，討論時間點i之前進行最多j交易的最佳解。

列一下轉移式即可以O(nk)解決(下面假設v[i]代表在i時的價格):

dp0[i][j]=max(dp1[i-1][j-1]+v[i],dp0[i-1][j])

dp1[i][j]=max(dp0[i-1][j]-v[i],dp1[i-1][j])

但是這次為何會想解這題，原因是其實早在好幾個月前早就看過一模一樣的題目，那時我完全沒想法(連nk解法都沒有)，但現在看發現以前那題n、k很大，可以都超過10^5，所以顯然需要另一種解法。

解法(2):一維DP+Aliens 優化，時間複雜度:O(nlogC)

這個解法可以忽視k大小，由於k和解大小的關係函數具凸性，所以可以使用Aliens優化，在每次DP假設一個penalty，代表每次交易的費用，透過二分搜penalty找到符合題意剛好k次的penalty，最後再把它加回去。

令dp[i]=pair(j,k)代表在時間點i之前最大值是j而需要k次交易

轉移式變成如下:

dp0[i]=max(dp1[i-1]+v[i]+額外費用,dp0[i-1])

dp1[i]=max(dp0[i-1]-v[i](買賣次數+1),dp1[i-1])

class Solution {

    int l,r,m;//for BIS , m -> penalty

    int ans,k,leng;

    int[] v=new int[1005];

    pair[] dp0=new pair[1005];//for DP

    pair[] dp1=new pair[1005];

    public int maxProfit(int k, int[] prices) {

        this.k=k;

        leng=prices.length;

        init(prices);

        return BIS();

    }

    

    public void init(int[] p) {

        ans=-1;

        l=-1005;

        r=1005;

        Arrays.fill(v,0);

        for(int i=0;i<1005;i++)dp0[i]=new pair();

        for(int i=0;i<1005;i++)dp1[i]=new pair();
        
            for(int i=1;i<=leng;i++)v[i]=p[i-1];

        dp0[0].x=0;

        dp0[0].y=0;

        dp1[0].x=-(1<<30);

        dp1[0].y=0;

    }

    

    public pair max(pair f,pair s) {

        if(f.x!=s.x)return (f.x>s.x)?f:s;

        return (f.y>s.y)?f:s;

    }

    

    public pair buy(pair f,int val) {

        return new pair(f.x-val+m,f.y);

    }

    

    public pair sell(pair f,int val) {

        return new pair(f.x+val,f.y+1);

    }

    

    public pair DP() {

        for(int i=1;i<=leng;i++) {

            dp1[i]=max(dp1[i-1],buy(dp0[i-1],v[i]));

            dp0[i]=max(dp0[i-1],sell(dp1[i-1],v[i]));

        }

        return dp0[leng];         

    }

    

    public int BIS() {

        pair dp;

        while(l!=r) {

            m=(l+r)>>1;//Penalty Binary Search

            dp=DP();

            if(dp.y<k) {

                l=m+1;

                ans=Math.max(ans,dp.x-m*(dp.y));

            }

            else r=m;    

        }

        m=l;

        return Math.max(ans,DP().x-m*k);

    }

}



class pair{

    int x=0,y=0;

    pair(){}

    pair(int a,int b){

        x=a;

        y=b;

    }

}