LeetCode DayDynamic Programming Part1
- 王林asal
- 2024-07-18 12:46:25744semak imbas
509. Nombor Fibonacci
Nombor Fibonacci, yang lazimnya dilambangkan F(n) membentuk jujukan, dipanggil jujukan Fibonacci, supaya setiap nombor ialah hasil tambah bagi dua nombor sebelumnya, bermula dari 0 dan 1. Iaitu,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), untuk n > 1.
Diberi n, hitung F(n).
Contoh 1:
Input: n = 2
Keluaran: 1
Penjelasan: F(2) = F(1) + F(0) = 1 + 0 = 1.
Contoh 2:
Input: n = 3
Keluaran: 2
Penjelasan: F(3) = F(2) + F(1) = 1 + 1 = 2.
Contoh 3:
Input: n = 4
Keluaran: 3
Penjelasan: F(4) = F(3) + F(2) = 2 + 1 = 3.
Kekangan:
0 <= n <= 30
Halaman Asal
Kaedah Rekursi
public int fib(int n) {
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else{
return fib(n-1) + fib(n-2);
}
}
Kaedah Rekursi adalah seperti DFS untuk pergi ke dalam dan kemudian melakukan backtracking untuk mendapatkan jawapan akhir.
masa: O(2^n)
ruang: O(1)
private int[] dp = new int[31];
public int fib(int n) {
if(n<2){
dp[n] = n;
return n;
}
if(n>=2 && dp[n]!=0){
return dp[n];
}
dp[n] = fib(n-1) + fib(n-2);
return dp[n];
}
</p>
<p>kita boleh menggunakan tatasusunan global untuk menyimpan hasil bagi mengelakkan pengulangan semula elemen yang sama. cth. rajah di bawah memaparkan bahawa f(17) dan f(18) ialah dua laluan rekursi yang berbeza dan jika kita menggunakan kaedah rekursi biasa kita perlu mengiranya lebih daripada sekali. </p>
<p><img src="https://img.php.cn/upload/article/000/000/000/172127798860260.png" alt="Image description" loading="lazy" style="max-width:90%" style="max-width:90%"></p>
<p>masa: O(n), ruang: O(n)</p>
<h2>
Pengaturcaraan Dinamik
</h2>
<pre class="brush:php;toolbar:false"> public int fib(int n) {
if(n<2){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
Rekursi berfungsi dari atas ke bawah dan kemudian menjejak ke belakang, rekursi memori akan menyimpan hasil rekursi untuk mengelakkan pengiraan berganda. Sekarang pengaturcaraan dinamik berfungsi dari bawah ke atas dan menyimpan hasil setiap langkah ke tatasusunan dp.
masa: O(n)
ruang: O(n)
Kita juga boleh mengemas kini nombor had secara dinamik dan bukannya tatasusunan. Ini akan menjimatkan kerumitan ruang, terutamanya untuk sejumlah besar elemen.
public int fib(int n) {
if(n<2){
return n;
}
int start = 0;
int pre = 1;
int res = pre;
for(int i=2; i<=n; i++){
res = start + pre;
start = pre;
pre = res;
}
return res;
}
70. Mendaki Tangga
Anda sedang menaiki tangga. Ia mengambil beberapa langkah untuk sampai ke puncak.
Setiap kali anda boleh mendaki 1 atau 2 anak tangga. Dalam berapa banyak cara yang berbeza anda boleh mendaki ke puncak?
Contoh 1:
Input: n = 2
Keluaran: 2
Penjelasan: Terdapat dua cara untuk mendaki ke puncak.
- 1 langkah + 1 langkah
- 2 langkah Contoh 2:
Input: n = 3
Keluaran: 3
Penjelasan: Terdapat tiga cara untuk mendaki ke puncak.
- 1 langkah + 1 langkah + 1 langkah
- 1 langkah + 2 langkah
- 2 langkah + 1 langkah
70. Mendaki Tangga
Anda sedang menaiki tangga. Ia mengambil beberapa langkah untuk sampai ke puncak.
Setiap kali anda boleh mendaki 1 atau 2 anak tangga. Dalam berapa banyak cara yang berbeza anda boleh mendaki ke puncak?
Contoh 1:
Input: n = 2
Keluaran: 2
Penjelasan: Terdapat dua cara untuk mendaki ke puncak.
- 1 langkah + 1 langkah
- 2 langkah Contoh 2:
Input: n = 3
Keluaran: 3
Penjelasan: Terdapat tiga cara untuk mendaki ke puncak.
- 1 langkah + 1 langkah + 1 langkah
- 1 langkah + 2 langkah
- 2 langkah + 1 langkah
Kekangan:
1 <= n <= 45
Halaman Asal
public int climbStairs(int n) {
if(n<3){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
if(n<3){
return n;
}
int prepre = 1;
int pre = 2;
int res = 0;
for(int i=3; i<=n; i++){
res = prepre + pre;
prepre = pre;
pre = res;
}
return res;
}
746. Kos Min Panjat Tangga
Anda diberi kos tatasusunan integer dengan kos[i] ialah kos langkah ke-1 pada tangga. Sebaik sahaja anda membayar kos, anda boleh memanjat satu atau dua anak tangga.
Anda boleh sama ada bermula dari langkah dengan indeks 0 atau langkah dengan indeks 1.
Kembalikan kos minimum untuk mencapai bahagian atas lantai.
Contoh 1:
Input: kos = [10,15,20]
Keluaran: 15
Penjelasan: Anda akan bermula pada indeks 1.
- Bayar 15 dan panjat dua anak tangga untuk sampai ke puncak. Jumlah kos ialah 15. Contoh 2:
Input: kos = [1,100,1,1,1,100,1,1,100,1]
Keluaran: 6
Penjelasan: Anda akan bermula pada indeks 0.
- Bayar 1 dan panjat dua anak tangga untuk mencapai indeks 2.
- Bayar 1 dan panjat dua anak tangga untuk mencapai indeks 4.
- Bayar 1 dan panjat dua anak tangga untuk mencapai indeks 6.
- Bayar 1 dan naik satu langkah untuk mencapai indeks 7.
- Bayar 1 dan naik dua anak tangga untuk mencapai indeks 9.
- Bayar 1 dan panjat satu langkah untuk sampai ke puncak. Jumlah kos ialah 6.
Kekangan:
2 <= kos.panjang <= 1000
0 <= kos[i] <= 999
Halaman Asal
public int minCostClimbingStairs(int[] cost) {
if(cost.length < 2){
return 0;
}
int[] dp = new int[cost.length+1];
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<dp.length; i++){
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[dp.length-1];
}
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`
Berhati-hati bahawa kita sepatutnya soalan telah memberitahu kita bahawa kita boleh bermula dari indeks 0 dan indeks 1, yang membayangkan jika bilangan tangga kurang daripada 2, kita akan kos 0 kerana kita boleh mula pada ketika itu dan tingkah laku permulaan akan kos 0, hanya tingkah laku kos bergerak.
Atas ialah kandungan terperinci LeetCode DayDynamic Programming Part1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!