。チケットの最低価格

983。チケットの最低価格

難易度: 中

トピック: 配列、動的プログラミング

あなたは 1 年前に鉄道旅行を計画しました。年間の旅行予定日は、整数配列の日数として指定されます。各日は 1 ～ 365 の整数です。

鉄道チケットは 3 つの異なる方法で販売されます:

• 1 日 パスは、コスト [0] ドルで販売されます。
• 7 日間 パスは [1] ドルで販売され、
• 30 日間 パスは、[2] ドルで販売されます。

パスを使用すると、その日数の連続旅行が可能になります。

• たとえば、2 日目に 7 日間 パスを取得した場合、2、3、4、5、6、7、8 日間の 7 日間旅行できます。

指定された日数のリストで毎日移動するのに必要な最小ドル数を返します。

例 1:

• 入力: 日数 = [1,4,6,7,8,20]、費用 = [2,7,15]
• 出力: 11
• 説明: たとえば、旅行計画に基づいてパスを購入する方法の 1 つを次に示します。
  • 1 日目に、1 日目をカバーするコスト [0] = $2 で 1 日パスを購入しました。
  • 3 日目に、3、4、...、9 日目をカバーする 7 日間パスを費用[1] = 7 ドルで購入しました。
  • 20 日目に、20 日目をカバーするコスト [0] = $2 で 1 日パスを購入しました。
  • 合計 11 ドルを費やし、旅行の全日数をカバーしました。

例 2:

• 入力: 日数 = [1,2,3,4,5,6,7,8,9,10,30,31]、費用 = [2,7,15]
• 出力: 17
• 説明: たとえば、旅行計画に基づいてパスを購入する方法の 1 つを次に示します。
  • 1 日目に、1、2、...、30 日をカバーする 30 日パスを費用[2] = 15 ドルで購入しました。
  • 31 日目に、31 日目をカバーする費用[0] = $2 で 1 日パスを購入しました。
  • 合計 17 ドルを費やし、旅行の全日数をカバーしました。

制約:

• 1
• 1
• 日数は厳密に増加順です。
• コスト.長さ == 3
• 1

解決策:

この問題には、年間を通して指定された一連の日に旅行するための最低費用を決定することが含まれます。この問題では、1 日パス、7 日パス、および 30 日パスの 3 種類の旅行パスが提供されており、それぞれに特定の費用がかかります。目標は、これらのパスを使用してすべての旅行日をカバーする最も安価な方法を見つけることです。このタスクでは、動的プログラミングを使用して最小コストを効率的に計算する必要があります。

重要なポイント

• 動的プログラミング (DP): 動的プログラミングを使用して、毎日の最小コストを追跡しています。
• 旅行日数: 旅行日数は厳密に昇順で提供されます。つまり、旅行する必要がある日数が正確にわかっています。
• 3 種類のパス: days 配列の各日 d について、現在の日 d をカバーするパスの購入コストを考慮して最小コストを計算します。
  • 1 日パス: 料金は、前日の料金 (dp[i-1]) に 1 日パスの料金 (costs[0]) を加算したものになります。
  • 7 日間パス: 料金は、7 日間パスの料金 (コスト[1]) に、d から 7 日以内の直近の日の料金を加算したものとなります。
  • 30 日パス: 料金は、d から 30 日以内の直近の日の料金に 30 日パスの料金 (コスト[2]) を加算したものとなります。
• 基本ケース: 旅行が行われない場合の 1 日の最低コストは 0 です。

アプローチ

1. DP 配列: DP 配列 dp[] を使用します。ここで、dp[i] は、i 日目までのすべての旅行日数をカバーする最小コストを表します。
2. DP 配列への入力: 1 から 365 までの毎日:
   • その日が旅行日の場合、以下を考慮して最小コストが計算されます。
     • 1 日パスの使用料金。
     • 7 日間パスの使用料金。
     • 30 日パスの使用料金。
   • その日が旅行日ではない場合、その日の料金は前日と同じになります (dp[i] = dp[i-1])。
3. 最終回答: DP 配列を入力した後、最小コストは dp[365] に保存されます。これは、考えられるすべての旅行日数をカバーします。

プラン

1. サイズ 366 の配列 dp[] を初期化します (365 日目までを処理するために 1 つ追加)。
2. 0 日目にはコストがかからないため、dp[0] を 0 に設定します。
3. 特定の日が旅行日かどうかを簡単に確認するには、travelDays セットを作成します。
4. 毎日 1 から 365 まで反復します。
   • 旅行日の場合は、各パスの種類を考慮して最低料金を計算します。
   • そうでない場合は、前日の費用を繰り越します。
5. dp[365] の値を返します。

このソリューションを PHP で実装してみましょう: 983。チケットの最低料金

<?php
/**
 * @param Integer[] $days
 * @param Integer[] $costs
 * @return Integer
 */
function mincostTickets($days, $costs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$days1 = [1, 4, 6, 7, 8, 20];
$costs1 = [2, 7, 15];
echo mincostTickets($days1, $costs1); // Output: 11

$days2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs2 = [2, 7, 15];
echo mincostTickets($days2, $costs2); // Output: 17
?>

説明：

• アルゴリズムは、1 年中毎日 (365 日) 繰り返されます。
• 旅行日ごとに、以下の方が安いかどうかを考慮してコストを計算します。
  • 1 日パスを購入します (前日の料金に 1 日パスの料金を追加します)。
  • 7 日間パスを購入します (7 日間パスの料金を追加し、過去 7 日間の旅行料金が考慮されます)。
  • 30 日パスを購入します (30 日パスの料金を追加し、過去 30 日間の旅行料金が考慮されます)。
• 旅行日でない場合、料金は前日と同じです。

チュートリアルの例

例 1:

入力:

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];

• 1 日目: 1 日パスを $2 で購入します。
• 4 日目: 7 日間パスを $7 で購入します (4 日目から 9 日目までが対象)。
• 20 日目: $2 でもう 1 日パスを購入します。

合計コスト = $2 $7 $2 = $11.

例 2:

入力:

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];

• 1 日目: 30 日パスを 15 ドルで購入します (1 日目から 30 日目までが対象)。
• 31 日目: 1 日パスを $2 で購入します。

総費用 = $15 $2 = $17.

時間計算量

解の時間計算量は O(365) です。これは、1 年中すべての日を反復処理し、毎日定数時間の操作 (移動日数の確認と DP の更新) を実行するためです。配列）。したがって、ソリューションは日数に対して直線的な時間で実行されます。

出力例

例 1:

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 11

例 2:

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 17

このソリューションは、動的プログラミングを使用して、旅行日数をカバーするための最小コストを効率的に計算します。数日間反復し、すべての可能なパス (1 日、7 日、30 日) を考慮することで、アルゴリズムはパスを購入するための最適な戦略を見つけます。時間計算量は日数に関して線形であるため、問題の制約に適しています。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。チケットの最低価格の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。