leetcode188。株式を売買するのに最適な時期IV
Leetcode 188 Best Time Buy
あなたがそのための配列を持っているとしましょう 私 thelementは、その日の特定の株式の価格です。 私 。
最大の利益を見つけるためのアルゴリズムを設計します。あなたはせいぜい完了することができますにトランザクション。
注意：
同時に複数の取引を行うことはできません（つまり、再度購入する前に株式を売却する必要があります）。
例1：
public int maxProfit(int k, int[] prices) { if(prices==null||prices.length==0) return 0 if(k>prices.length/2) return maxProfit2(prices)//Convert to question 2 int[][] dp=new int[k+1][prices.length] for(int i=1i例2：
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
この質問は121よりも難しいです。株式を売買するのに最適な時期、122。株式を売買するのに最適な時期II。何回かわかりません。
ディスカッションエリアでしか偉大な神の答えを見ることができません。 2次元のdpを使用できることを知ってください。 dp [i] [j]では、iはトランザクションの数を表し、jは現在までの日数を表し、dp [i] [j]はこの時点での最大利益を表します。重要なのは、どのように再帰的になるかです。 ？ ？
2つのケースがあります：
1.最終日に在庫が売却されなかった場合。 dp [i] [j] = dp [i] [j-1]。
2.最終日に株式を売却する場合。 dp [i] [j] = max（dp [i-1] [jpre] + prices [j] -prices [jpre]）、jpreは前日の価格です。ここでは、jpreが-1日より前にiを取引したことを意味します。時間、最後のトランザクションはprices [j] -prices [jpre]です。このようにして、最大jpre値は毎回計算されますか？ ？上記の式をdp [i] [j] = prices [j] + max（dp [i-1] [jpre] -prices [jpre]）に変更します。これには利点があります、 jをトラバースするときに最大dp [i-1] [jpre] -prices [jpre]を維持できるため、毎回計算する必要はありません。
したがって、総再帰はdp [i] [j] = max（dp [i] [j-1]、prices [j] + max（dp [i-1] [jpre] -prices [jpre]））です。
初期条件：dp [0] [j] = 0 dp [i] [0] = 0。
ここでは、メモリオーバーフローの問題も考慮する必要があります。 kの値が大きすぎる場合（k> prices.length / 2）、問題はリートコード122になります。株式を売買するのに最適な時期II。トランザクションはいくつでも実行できます。
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
私はこの問題の解決策を考えていませんでした。主な理由は、再帰について考えていなかったからです。 再帰式はさまざまな状況を分析しますが、さまざまな状況を見つける方法は？現在の問題の最後のステップでさまざまな状況を検討できる場合があります 。最後のステップから始めて、これが最終日の在庫の処理であり、2つの状況とサブ問題を分析することによって関係が確立されます。これは、最後の文字のさまざまな処理状況を考慮して開始された編集距離の問題にいくぶん似ています。
この質問のもう1つの難しさは、再帰式を解くときのトリックです。 max（dp [i-1] [jpre] -prices [jpre]）を見つけるために再度トラバースする必要はありません。トラバース時に自動的に更新され、二重カウントも削減されます。 二重計算を減らすことは、多くの場合、時間の複雑さを減らすための本質です。 。経験が必要です。