其他:

今日總結
往期打卡

---

背包問題特點:

滾動數組背包遍歷順序

• 完全背包從小到大,即基于當前物品更新過的繼續更新
• 01背包從大到小,即基于上一物品更新

物品內外層循環:

• 求組合數外層for循環遍歷物品，內層for遍歷背包。
  (物品順序固定,所以不會出現不同的排列)
• 求排列數外層for遍歷背包，內層for循環遍歷物品。

518. 零錢兌換 II

跳轉: 518. 零錢兌換 II

學習: 代碼隨想錄公開講解

問題:

給你一個整數數組 coins 表示不同面額的硬幣，另給一個整數 amount 表示總金額。

請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。

假設每一種面額的硬幣有無限個。

題目數據保證結果符合 32 位帶符號整數。

思路:

完全背包求組合數,外側物品,順序從小到大遍歷

復雜度:

• 時間復雜度: $O(nm)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int num = 0; num < coins.length; num++) {for (int i = coins[num]; i <= amount; i++) {dp[i] += dp[i - coins[num]];}}return dp[amount];}
}

---

377. 組合總和 Ⅳ

跳轉: 377. 組合總和 Ⅳ

學習: 代碼隨想錄公開講解

問題:

給你一個由 不同 整數組成的數組 nums ，和一個目標整數 target 。請你從 nums 中找出并返回總和為 target 的元素組合的個數。

題目數據保證答案符合 32 位整數范圍。

思路:

完全背包求排列數,外側背包,順序從小到大遍歷

復雜度:

• 時間復雜度: $O(nm)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int num = 0; num < nums.length; num++) {if(i>=nums[num]){dp[i] += dp[i - nums[num]];}}}return dp[target];}
}

---

790. 多米諾和托米諾平鋪(每日一題)

跳轉: 790. 多米諾和托米諾平鋪

問題:

有兩種形狀的瓷磚：一種是 2 x 1 的多米諾形，另一種是形如 “L” 的托米諾形。兩種形狀都可以旋轉。

給定整數 n ，返回可以平鋪 2 x n 的面板的方法的數量。返回對 109 + 7 取模 的值。

平鋪指的是每個正方形都必須有瓷磚覆蓋。兩個平鋪不同，當且僅當面板上有四個方向上的相鄰單元中的兩個，使得恰好有一個平鋪有一個瓷磚占據兩個正方形。

思路:

可以看作背包問題,1有1個,2有1個,3有2個,4有2個,從3中間插兩個橫牌是5,有兩個,4插兩個橫牌是6,有兩個,依此類推后面都有兩個

這題就是完全背包求排列

也可以看作是爬樓梯

$$f(n)=f(n?1)+f(n?2)+\sum _{m=0}^{n?3}f(m)?2$$
求通項公式為
$$f(n)=2?f(n?1)+f(n?3)$$

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼(遞推公式):

class Solution {private static final int MOD = 1_000_000_007;public int numTilings(int n) {if (n == 1) {return 1;}long[] f = new long[n + 1];f[0] = f[1] = 1;f[2] = 2;for (int i = 3; i <= n; i++) {f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;}return (int) f[n];}
}

復雜度:

• 時間復雜度: $O(n^2)$
• 空間復雜度: $O(n)$

代碼(完全背包求組合):

class Solution {public int numTilings(int n) {int[] dp = new int[n+1];long MOD = 1000000007;dp[0] = 1;for(int i=1;i<=n;i++){for(int j=1;j<=2&&j<=n;j++)if(i>=j)dp[i]=(int)(((long)dp[i]+dp[i-j])%MOD);for(int j=3;j<=n;j++)if(i>=j)dp[i]=(int)(((long)dp[i]+2*dp[i-j])%MOD);}return dp[n];}
}

---

57. 爬樓梯（第八期模擬筆試）

跳轉: 57. 爬樓梯（第八期模擬筆試）

學習: 代碼隨想錄公開講解

問題:

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

每次你可以爬至多m (1 <= m < n)個臺階。你有多少種不同的方法可以爬到樓頂呢？

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

思路:

完全背包求排列

復雜度:

• 時間復雜度: $O(nm)$
• 空間復雜度: $O(n)$

代碼:

import java.util.Scanner;
class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] dp = new int[n+1];dp[0] = 1;for(int j=1;j<=n;j++)for(int i=1;i<=m;i++)if(j>=i)dp[j] += dp[j-i];System.out.println(dp[n]);}
}

---

總結

練習了完全背包問題和背包問題求排序組合

往期打卡

代碼隨想錄算法訓練營第三十一天

代碼隨想錄算法訓練營第三十天(補)

代碼隨想錄算法訓練營第二十九天

代碼隨想錄算法訓練營第二十八天

代碼隨想錄算法訓練營第二十七天(補)

代碼隨想錄算法訓練營第二十六天

代碼隨想錄算法訓練營第二十五天

代碼隨想錄算法訓練營第二十四天

代碼隨想錄算法訓練營第二十三天

代碼隨想錄算法訓練營周末四

代碼隨想錄算法訓練營第二十二天(補)

代碼隨想錄算法訓練營第二十一天

代碼隨想錄算法訓練營第二十天

代碼隨想錄算法訓練營第十九天

代碼隨想錄算法訓練營第十八天

代碼隨想錄算法訓練營第十七天

代碼隨想錄算法訓練營周末三

代碼隨想錄算法訓練營第十六天

代碼隨想錄算法訓練營第十五天

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天