Shannon's Blog 🐟 技術 | 生活 | 旅行

1 題目描述 給定一個m x n的矩陣，找到一條從左上角到右下角的最小路徑和。每次只能向右或是向下移動。 2 解法 這題與LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南的題目類似，如果你會做Leetcode-62-Unique Paths，這題也是一樣的概念，只是這題是找最小路徑和。 2.1 Recursive 首先我們很清楚，我們只能往右或是往下走，假設i是row，j是column， 所以我們可以寫出以下的關係式 往右：helper(i, j+1) column + 1 往下：helper(i+1, j) row + 1 然後關係式：min(往右, 往下) + 當前 1min(helper(i, j+1), helper(i+1, j)) + grid[i][j] 接下來我們來解決最小問題的狀況： 如果只有一行或是一列，直接回傳總和，因為只有一條路可以走 何時知道走到底，當i==rows-1和j==cols-1時，就是走到底了，直接回傳grid[i][j] 12if i == rows-1 and j == cols-1: ...

1 題目描述 給定一個三角形，找到從頂部到底部的最小路徑和。每一步只能移動到下一行的相鄰元素上。 2 解法 其實這題與leetcode #300 Longest Increasing Subsequence有點類似，如果我們嘗試用樹狀圖，把所有可能寫出來，如果今天題目是[[1], [2,3], [4,5,6], [7,8,9,10]]大概會長以下這樣： 特徵如下： 從底部慢慢往上走，算出每層由下往上的最佳解 dp 的值是由下往上的最佳解 2.1 Recursion 但我們先慢慢來吧，先寫出Recursion的寫法。他的問題也是經典的拿與不拿問題。題目可以看到，如果我這一層layer取i，那我下一層layer只能取i或是i+1，這兩個選最小的。 其實Recursive的關係式 (helper是recursive的function) 1min(helper(layer+1, i), helper(layer+1, i+1)) + triangle[layer][i] 那最小問題基本上就是當已經走到底了，直接回傳triangle[layer][i]，因為這時候就是最底層了，不用再往 ...

前言 CSND | 提高SVM分類器的準確率 目前，因為論文的主要題目是做法律文件的機器學習分類，但是因為資料量少，碰到一點瓶頸。所以整理了一些提高分類器準確度的方法，但是注意的是本篇內容主要針對傳統的機器學習像是SVM, RF, NB等，並非Deep Learning。主要有以下： 特徵工程：選擇更好的特徵 調整超參數：可以透過找到最佳的超參數組合，來提高分類器的準確率 數據清洗與預處理：數據清洗是機器學習中非常重要的一個環節，數據清洗的好壞直接影響到模型的準確率 使用核函數：有些模型像是SVM可以使用不同的核函數，來提高分類器的準確率，例如線性核函數、多項式核函數、高斯核函數等 集成學習：使用集成學習如Bagging、Boosting等方法，來提高分類器的準確率 增加訓練數據：增加訓練數據，可以提高分類器的準確率，特別是針對複雜的問題 調整超參數 你是否曾經覺得模型有太多的超參數而感到厭煩嗎？要從某一個演算法得到好的解必須要調整超參數，所謂的超參數就是控制訓練模型的一組神秘數字，例如學習速率就是一種超參數。你永遠都不知道 0~1 之間哪一個數字是最適合的，唯一的方法就是試錯 ...

1 題目描述 這是我的第一次參加 LeetCode Contest，這次的題目是一道簡單的滑動窗口問題，給定一個數組nums和一個整數k，你需要針對大小為 k 的所有子陣列計算它們的 “power”： 如果子陣列的所有元素是連續且按升序排列，則該子陣列的 power 是其最大元素。 如果子陣列的元素不符合條件，則返回 -1。 2 解法 2.1 我的解法 我一開始的想法很簡單，我需要有一個function負責檢查是否為連續且按升序排列，如果是就返回最後一個數值，如果不是就返回-1。 12345def helper(sub_nums: List[int]) -> int: for j in range(1, k): if sub_nums[j - 1] + 1 != sub_nums[j]: return -1 return sub_nums[-1] 接下來我們只要根據 k 的長度，把數組分成大小為 k 的子陣列，然後檢查每個子陣列是否符合條件，如果符合就找出最大值，如果不符合就返回-1。 12345678910111213141 ...

1 題目描述 給定一個整數數組nums，找到一個最長的遞增子序列的長度。 2 解法 2.1 Recursion 這題是DP問題，假設我們有一組數字[1, 2, 3, 7, 4, 5, 6] 我們需要比較當前的值 nums[i]是否比上一個值 last還要大，當滿足條件的時候，我們就要思考一個問題到底是**要把當前的值考量進去，還是跳過當前的？**這就會牽涉到兩個公式，類似背包問題，偷與不偷，那這裡就是塞與不塞： 塞： 1塞(當前值) + 未來的最佳解 不塞： 不塞 + 未來的最佳解 以上述的例子來說，如果我們走到 7 的時候，我們可以選擇塞或不塞 如果塞的話，未來的最佳解都是 0，因為沒有比7大的值了 如果不塞的話，後面還有4, 5, 6可以選擇 這樣的話我們可以得出一個公式，假設i是當前的值： 塞： 1 + helper(nums[i+1:]) 不塞： helper(nums[i+1:]) 但是還有一個問題需要考慮，就是我們在往後比較的時候，需要知道被比較的對象是誰，舉例來說一樣從7開始 塞：那後續與4, 5, 6比較的就是7 不塞：那後續與4比較的就是3，與5比較的 ...

1 題目描述 給定不同面額的硬幣coin和一個總金額amount，寫一個函數來計算可以製造出總金額的最少硬幣數量。如果無法製造出總金額，則返回-1。 2 解法 其實dp的題目中有個共通點，都像是書包題目，為什麼是 dp 問題是因為可以拆分成小問題，而 amount 的小問題基本上就是 range(1, amount+1) 這些範圍如果都能夠找到最佳解ㄝ那自然amount也能找到最佳解。所以我們腦子有個思路，就是我們可以先從1開始。而最小值就是0，因為0元不需要硬幣。 小問題開始 123456# 初始化 dp 碰到 0 的 amount 就是 0dp = {0: 0} # 因為 range 是不包含最後一個數字，所以要 +1 for i in range(1, amount+1): # 初始化 dp[i] 為無限大 dp[i] = float('inf') 接下來，我們假設: amount=11 且 coins=[3, 5]，我們可以看到dp的變化如下： dp[0] = 0 dp[1] = inf 沒有對應的 coin dp[2] ...

1 題目描述 這題簡單來說就是給定一個字串s和一個字典wordDict，判斷s是否可以被空格分割成一個或多個在字典中出現的單詞。 2 解法 2.1 我的作法 但是這個為什麼說他是一個dp問題，是因為他就像背包問題一樣，s是背包，wordDict是物品，我們要看看s能不能裝下wordDict裡面的物品。如果裝錯物品可能導致裝不下。 我的想法一開始是一個用切割的方式切成兩塊，然後把所有可能的組合都存到字典裡面，最後找到可以把目前切割結果組合成s的組合。 切割成兩塊 例如：applepenapple a + pplepenapple ap + plepenapple app + lepenapple … 123for i in range(1, n): check_w = word[0:i] rest_w = word[i:n] 如果找到一組，切成兩塊的結果都是True就找到了 假設helper是一個可以判斷是否可以切割成wordDict的函數 關係式：helper(word[0:i]) and helper(word[i:n]) 12345for i in ran ...

1 題目描述 有一排房子，每個房子裡面有一定的錢，但是不能連續偷兩個房子，否則會報警，在不觸發報警的狀況下求最多可以偷到多少錢。 2 解法 按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是： Step1: Recursive Step2: Recursive with Memoization Step3: Iterative + Tabulation Step4: Iterative with Constant Space Step1: Recursive 一道很典型的通過子問題去解決原問題的題目，所以可以透過遞歸以及動態規劃解決。 假設：知道了前 n - 1 家店最多能偷的錢數，前 n - 2 家店最多能偷的錢數。 關係式：如果我們想要知道前 n 家商店最多能偷多少錢，我們可以選擇偷 偷：偷第 n 家商店 + 前 n - 2 家商店最多能偷的錢數。 不偷：不偷第 n 家商店 + 前 n - 1 家商店最多能偷的錢數。 最小問題：如果今天 n = 0，那麼就是0，如果n = 1 ...

1 題目描述 爬樓梯，每次可以爬一階或是兩階，求爬到第n階有幾種方法。 2 解法 按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是： Step1: Recursive Step2: Recursive with Memoization Step3: Iterative + Tabulation Step4: Iterative with Constant Space Step1: Recursive 最基本也是最蠢的就是我們要先發現，基本上走樓梯的方法數量是f(n) = f(n-1) + f(n-2)，這樣的遞迴式，我們可以直接寫出來。 123456def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2) Step2: Recursive with Memoization 那我們就思考，是不 ...

前言 我希望可以熟悉DP的思維，剛好看到這篇Medium | Ultimate Guide to Dynamic Programming獲得蠻多的讚，所以打算這篇為基礎做筆記。 在解決Dynamic Programming重要的前提是： 耐心: DP問題通常需要花時間來思考，不要急著寫程式 熟悉遞迴: DP問題通常可以用遞迴的方式來解決，因此熟悉遞迴是很重要的 Recursion遞迴跟DP的不同 遞歸和動態規劃的主要關聯在於： 重疊子問題：如果一個遞歸算法在計算過程中重複解決相同的子問題，可以使用動態規劃來優化。這時，遞歸算法可以轉化為帶備忘錄的遞歸（自頂向下的動態規劃）。 最優子結構：如果一個問題的最優解可以由其子問題的最優解構成，那麼可以使用動態規劃來解決這個問題。 有一個很簡單的例子，使用Fibonacci數列來說明這兩個概念。 Fibonacci數列的遞歸解法123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) ...