斐波那契數列

---

目錄

爬樓梯

強盜搶劫

強盜在喚環形街區搶劫

信件錯排

注：具體解析請點擊鏈接進入LeetCode題解區。

---

1. 爬樓梯

https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

public int climbStairs(int n) {if (n == 1) {return 1;}int[] dp = new int[n + 1];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 climbStairs2(int n) {if (n <= 2) {return n;}int pre2 = 1;int pre1 = 2;for (int i = 3; i <= n; i++) {int cur = pre1 + pre2;pre2 = pre1;pre1 = cur;}return pre1;}

---

2. 強盜搶劫

題目描述：搶劫一排住戶，但是不能搶鄰近的住戶，求最大搶劫量。

定義 dp 數組用來存儲最大的搶劫量，其中 dp[i] 表示搶到第 i 個住戶時的最大搶劫量。
由于不能搶劫鄰近住戶，如果搶劫了第 i -1 個住戶，那么就不能再搶劫第 i 個住戶，所以

public int rob(int[] nums) {int pre2 = 0, pre1 = 0;for (int i = 0; i < nums.length; i++) {int cur = Math.max(pre2 + nums[i], pre1);pre2 = pre1;pre1 = cur;}return pre1;}

---

3. 強盜在喚環形街區搶劫

https://leetcode-cn.com/problems/house-robber-ii

題目描述：你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;if (n == 1) {return nums[0];}return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));}private int rob(int[] nums, int first, int last) {int pre=0,cur=0,tmp;for (int i = first; i <= last; i++) {tmp = cur;cur = Math.max(cur,pre+nums[i]);pre = tmp;}return cur;}

---

4. 信件錯排

題目描述：定義一個數組 dp 存儲錯誤方式數量，dp[i] 表示前 i 個信和信封的錯誤方式數量。假設第 i 個信裝到第 j 個信封里面，而第 j 個信裝到第 k 個信封里面。

根據 i 和 k 是否相等，有兩種情況：

• i==k，交換 i 和 k 的信后，它們的信和信封在正確的位置，但是其余 i-2 封信有 dp[i-2] 種錯誤裝信的方式。由于 j 有 i-1 種取值，因此共有 (i-1)*dp[i-2] 種錯誤裝信方式。
• i != k，交換 i 和 j 的信后，第 i 個信和信封在正確的位置，其余 i-1 封信有 dp[i-1] 種錯誤裝信方式。由于 j 有 i-1種取值，因此共有 (i-1)*dp[i-1] 種錯誤裝信方式。

綜上所述，錯誤裝信數量方式數量為：

public int errorNum(int n) {if (n == 0) {return 0;}int[] f = new int[n + 1];f[0] = 0;f[1] = 0;f[2] = 1;for (int i = 3; i <= n; i++) {f[i] = (i - 1) * f[i - 2] + (i - 1) * f[i - 1];}return f[n];}

總結

以上是生活随笔為你收集整理的LeetCode——动态规划：斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。