. Kos Minimum Untuk Tiket

983. Kos Minimum Untuk Tiket

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik

Anda telah merancang perjalanan kereta api setahun lebih awal. Hari dalam tahun di mana anda akan mengembara diberikan sebagai hari tatasusunan integer. Setiap hari ialah integer dari 1 hingga 365.

Tiket kereta api dijual dalam tiga cara berbeza:

• pas 1 hari dijual dengan kos[0] dolar,
• pas 7 hari dijual dengan kos[1] dolar dan
• pas 30 hari dijual dengan kos[2] dolar.

Pas membenarkan perjalanan selama beberapa hari berturut-turut.

• Sebagai contoh, jika kita mendapat pas 7 hari pada hari ke-2, maka kita boleh melakukan perjalanan selama 7 hari: 2, 3, 4, 5, 6, 7 dan 8.

Pulangan jumlah minimum dolar yang anda perlukan untuk perjalanan setiap hari dalam senarai hari yang diberikan.

Contoh 1:

• Input: hari = [1,4,6,7,8,20], kos = [2,7,15]
• Output: 11
• Penjelasan: Contohnya, berikut ialah satu cara untuk membeli pas yang membolehkan anda mengembara pelan perjalanan anda:
  • Pada hari 1, anda membeli pas 1 hari untuk kos[0] = $2, yang meliputi hari 1.
  • Pada hari ke-3, anda membeli pas 7 hari untuk kos[1] = $7, yang meliputi hari ke-3, 4, ..., 9.
  • Pada hari ke-20, anda membeli pas 1 hari untuk kos[0] = $2, yang meliputi hari ke-20.
  • Secara keseluruhan, anda membelanjakan $11 dan menampung semua hari perjalanan anda.

Contoh 2:

• Input: hari = [1,2,3,4,5,6,7,8,9,10,30,31], kos = [2,7,15]
• Output: 17
• Penjelasan: Contohnya, berikut ialah satu cara untuk membeli pas yang membolehkan anda mengembara pelan perjalanan anda:
  • Pada hari pertama, anda membeli pas 30 hari untuk kos[2] = $15 yang meliputi hari 1, 2, ..., 30.
  • Pada hari ke-31, anda membeli pas 1 hari untuk kos[0] = $2 yang meliputi hari ke-31.
  • Secara keseluruhan, anda membelanjakan $17 dan menampung semua hari perjalanan anda.

Kekangan:

• 1
• 1
• hari semakin meningkat.
• kos.panjang == 3
• 1

Penyelesaian:

Masalahnya melibatkan penentuan kos minimum untuk perjalanan pada set hari tertentu sepanjang tahun. Masalahnya menawarkan tiga jenis pas perjalanan: pas 1 hari, 7 hari dan 30 hari, setiap satu dengan kos tertentu. Matlamatnya adalah untuk mencari cara termurah untuk menampung semua hari perjalanan menggunakan pas ini. Tugas itu memerlukan penggunaan pengaturcaraan dinamik untuk mengira kos minimum dengan cekap.

Perkara Utama

• Pengaturcaraan Dinamik (DP): Kami menggunakan pengaturcaraan dinamik untuk menjejaki kos minimum untuk setiap hari.
• Hari Perjalanan: Hari perjalanan disediakan dalam susunan yang semakin meningkat, bermakna kami tahu dengan tepat hari mana kami perlu mengembara.
• Tiga Jenis Pas: Untuk setiap hari d dalam tatasusunan hari, kira kos minimum dengan mengambil kira kos membeli pas yang meliputi hari semasa d:
  • Pas 1 hari: Kos ialah kos pas 1 hari (kos[0]) ditambah pada kos hari sebelumnya (dp[i-1]).
  • Pas 7 hari: Kos ialah kos pas 7 hari (kos[1]) ditambah pada kos hari terbaharu iaitu dalam tempoh 7 hari dari hari d.
  • Pas 30 hari: Kos ialah kos pas 30 hari (kos[2]) yang ditambahkan pada kos hari terbaharu iaitu dalam tempoh 30 hari selepas d.
• Kes Asas: Kos minimum untuk sehari apabila tiada perjalanan dilakukan ialah 0.

Pendekatan

1. Susun DP: Kami akan menggunakan tatasusunan DP dp[] dengan dp[i] mewakili kos minimum untuk menampung semua hari perjalanan sehingga hari i.
2. Mengisi Tatasusunan DP: Untuk setiap hari dari 1 hingga 365:
   • Jika hari itu adalah hari perjalanan, kami mengira kos minimum dengan mempertimbangkan:
     • Kos menggunakan pas 1 hari.
     • Kos menggunakan pas 7 hari.
     • Kos menggunakan pas 30 hari.
   • Jika hari itu bukan hari perjalanan, kos untuk hari itu akan sama seperti hari sebelumnya (dp[i] = dp[i-1]).
3. Jawapan Akhir: Selepas mengisi tatasusunan DP, kos minimum akan disimpan dalam dp[365], yang meliputi semua hari perjalanan yang mungkin.

Rancang

1. Mulakan dp tatasusunan[] bersaiz 366 (satu tambahan untuk dikendalikan sehingga hari ke 365).
2. Tetapkan dp[0] kepada 0, kerana tiada kos untuk hari 0.
3. Buat set TravelDays untuk menyemak dengan cepat sama ada hari tertentu ialah hari perjalanan.
4. Lelaran setiap hari dari 1 hingga 365:
   • Jika hari perjalanan, kira kos minimum dengan mempertimbangkan setiap jenis pas.
   • Jika tidak, bawa ke atas kos hari sebelumnya.
5. Kembalikan nilai pada dp[365].

Mari laksanakan penyelesaian ini dalam PHP: 983. Kos Minimum Untuk Tiket

<?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
?>

Penjelasan:

• Algoritma berulang setiap hari dalam setahun (365 hari).
• Untuk setiap hari perjalanan, ia mengira kos dengan mempertimbangkan sama ada ia lebih murah untuk:
  • Beli pas 1 hari (menambah kos pas 1 hari kepada kos hari sebelumnya).
  • Beli pas 7 hari (menambah kos pas 7 hari dan mempertimbangkan kos perjalanan pada 7 hari lalu).
  • Beli pas 30 hari (menambah kos pas 30 hari dan mempertimbangkan kos perjalanan sepanjang 30 hari lalu).
• Jika bukan hari perjalanan, kos tetap sama seperti hari sebelumnya.

Contoh Panduan

Contoh 1:

Input:

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

• Hari 1: Beli pas 1 hari dengan harga $2.
• Hari 4: Beli pas 7 hari dengan harga $7 (cover hari 4 hingga 9).
• Hari 20: Beli pas 1 hari lagi dengan harga $2.

Jumlah kos = $2 $7 $2 = $11.

Contoh 2:

Input:

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

• Hari 1: Beli pas 30 hari dengan harga $15 (cover hari 1 hingga 30).
• Hari 31: Beli pas 1 hari dengan harga $2.

Jumlah kos = $15 $2 = $17.

Kerumitan Masa

Kerumitan masa penyelesaiannya ialah O(365), kerana kami mengulangi semua hari dalam setahun, dan untuk setiap hari, kami melakukan operasi masa yang berterusan (menyemak hari perjalanan dan mengemas kini DP tatasusunan). Oleh itu, penyelesaian berjalan dalam masa linear berbanding bilangan hari.

Output untuk Contoh

Contoh 1:

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

Contoh 2:

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

Penyelesaian dengan cekap mengira kos minimum untuk menampung hari perjalanan menggunakan pengaturcaraan dinamik. Dengan mengulangi sepanjang hari dan mempertimbangkan semua kemungkinan pas (1 hari, 7 hari, 30 hari), algoritma mencari strategi optimum untuk membeli pas. Kerumitan masa adalah linear dari segi bilangan hari, menjadikannya sesuai untuk kekangan masalah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Kos Minimum Untuk Tiket. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!