本文同步更新於個人網站中,有更好的排版和程式碼區塊 highlighting 支援。 接續昨天的文章,今天我們繼續來練習動態規劃的題目,熟悉一下動態規劃的解...
概念 動態規劃,簡稱 DP,是一種演算法的設計概念。其核心思想是通過解決許多相似性質的小問題,來計算我們所關心的大問題的答案。通常,這些小問題之間存在著遞迴關係...
繼第 5 天的「15. 3Sum」,今天來解 53 這題!還沒看過第 5 天或再之前天數的朋友,歡迎也去看看~ 話不多說,我們開始吧! 基本資訊 難度: M...
題目說明:給你一個三角形的陣列,要求出從最上層到最底層的最小總和,要注意的是往下加的時候橫列的位置只能維持和原本一樣或是往右一格。 Case 1:Input:...
題目說明:給一個整數n要你求出前n列的帕斯卡三角形。帕斯卡三角如下: Case 1:Input: numRows = 5Output: [[1],[1,1],[...
問題 這邊一樣以 AtCoder Educational DP Contest 的類題來舉例,這題是 B - Frog 2,簡單來說一隻青蛙可以一次走 ~...
問題 這邊以 AtCoder Educational DP Contest 的類題來舉例,這題是 A - Frog 1,簡單來說一隻青蛙可以一次走兩步或是走一步...
嗨~ 今天要來分享我是如何解2D的動態規劃問題。所謂的2D就是要考慮的因素(會影響到每個子問題結果)變多了。以前分享過的1D動態規劃,基本上只需要考慮子問題間的...
今天要繼續攻略1D動態規劃,所謂的1D指的是我們可以用一維的陣列儲存子問題的解或表達子問題。並且今天會著重使用True Dynamic Programming(...
終於來到最後一篇介紹 LeetCode 演算法的導讀文了,先聲明其實還有一些主題沒有介紹,在安排三十天挑戰計畫裡面,因為整個主題不是全部 LeetCode,是環...
在介紹完Backtracking後,我們接下來要介紹動態規劃的攻略。在解動態規劃或是Backtracking的題目時,我們都會用到決策樹(decision tr...
Hi,昨天分享了一些光看題目就知道很適合利用2D動態規劃去解決的問題。今天要繼續來分享屬於2D動態規劃的經典問題,和相關應用。 0/1背包問題 敘述: 有一...
問題 這邊一樣以 AtCoder Educational DP Contest 的類題來舉例,這題是 D - Knapsack 1,題意大概是有一個背包,裡面只...
問題 這邊一樣以 AtCoder Educational DP Contest 的類題來舉例,這題是 C - Vacation,題意簡單來說就是每天都可以進行一...
Hi大家好,今天要繼續介紹2D動態規劃裡面很經典的問題,你會發現有很多動態規劃的問題都有相似的pattern。 Longest Common Subseque...