Zako's Blog

題目網址：https://leetcode.cn/problems/longest-palindromic-subsequence/ 題意：給一 string s, 找出其中最長的回文 subsequence, 並返回該 subsequence 的長度。 subsequence：不改變 char 順序的情況下, 刪除某些 char 或者不刪除任何 char 形成的一個 sequence。 Solution： 想法：利用 DP 1. 定義狀態： 首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態 dp[i][j]：區間 s[i:j] 中最長回文 subseq 之長度 2. 得到轉移方程： 若 s[i] == s[j], 則取出小區間 s[i + 1][j - 1] + 2➔ dp[i][j] = dp[i + 1][j - 1] + 2 否則, 取 dp[i][j - 1]、dp[i + 1][j] 這兩個小區間中較大者➔ dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) 3. 初始化： dp[i][i]：當區間中只有一個 ...

題目網址：https://leetcode.cn/problems/filling-bookcase-shelves/ 題意：給一整數 array books,其中 books[i] = [thickness_i, height_i] 表示第 i 本書的厚度和高度。且會得到一個整數 shelfWidth。 按順序將這些書擺放到總寬度為 shelfWidth 的書架上。 先選幾本書放在書架上（它們的厚度之和小於等於書架的寬度 shelfWidth）, 然後再建一層書架。重覆這個過程, 直到把所有的書都放在書架上。 需要注意的是, 在上述過程的步驟中, 擺放書的順序須與整理好的順序相同。 例如, 如果有 5 本書, 那麼可能的一種擺放情況是：第一和第二本書放在第一層書架上, 第三本書放在第二層書架上, 第四和第五本書放在最後一層書架上。 返回以這種方式布置書架的最小高度。 Solution： 想法：利用 DP 1. 定義狀態： 首先, 會在 books 前先加上一個 0, 代表什麼元素都沒有的狀態 dp[i]：代表 books[1:i] 中布置書架的最小高度 2. 得到轉移 ...

題目網址：https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/ 題意：給一整數 array, 返回其 non-empty subarray（連續元素）在執行最多一次的刪除操作後, 所能得到的最大元素總和。 注意：刪除一個元素後的 subarray 不能為空。 Solution 1： 想法：利用 DP 1. 定義狀態： 首先, 會在 arr 前先加上一個 0, 代表什麼元素都沒有的狀態 noDel[i]：arr[1:i] 中, 沒有任何刪除操作的最大 subarray 和 oneDel[i]：arr[1:i] 中, 有一次刪除操作的最大 subarray 和 2. 得到狀態轉移方程： noDel[i]：由於沒有刪除操作, 故 arr[i] 一定在 subarry 中, 因此有兩種可能 以 arr[i] 為結尾, 所有往前延伸之 subarray 中最大的（subarray.size() > 1） ➔ 遞迴調用 noDel[i - 1] + arr[i] 只有 arr[i]（前面 ar ...

題目網址：https://leetcode.cn/problems/largest-divisible-subset/ 題意：給一無重覆正整數組成的集合 nums, 找出並返回其中最大的整除 subset answer, 使得其中每一個 pair (answer[i], answer[j]) 都應當滿足： answer[i] % answer[j] == 0 或 answer[j] % answer[i] == 0 如果存在多個 subset, 則返回其中一個即可。 Solution： 想法：利用 DP 1. 定義狀態： 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態 dp[i]：在 nums 為升序的前提下, 代表 nums[1:i] 中以 nums[i] 為結尾的最大整除 subset 之長度 prev[i]：代表 nums[i] 是由哪一個 idx 的狀態轉移過來的, 以便回溯找出整個 subset 2. 得到轉移方程： 若 nums[i] % nums[j] == 0：則 dp[i] = max(dp[i], dp[j] + 1), 其中 ...

題目網址：https://leetcode.cn/problems/max-consecutive-ones-ii/ 題意：給一 binary array nums, 你最多能反轉一個 0, 返回最大連續 1 的個數。 Solution 1： 想法：利用 DP 1. 定義狀態： 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態 flip[i] 為 nums[1:i] 中某個元素反轉後, nums[i] = 1 的最大連續 1 個數 noFlip[i] 為 nums[1:i] 中沒有任何元素反轉, nums[i] = 1 的最大連續 1 個數 2. 得到狀態轉移方程： 當 nums[i] == 0： flip[i] 必須使 nums[i] = 1, 故將 flip 的次數用在 nums[i] 上 ➔ flip[i] = noFlip[i - 1] + 1 noFlip[i] 必須使 nums[i] = 1, 但是在不 flip 的情況下, nums[i] 不可能為 1 ➔ noFlip[i] = 0 當 nums[i] == 1： flip[i] ...