Early return & Memoize

Early return(優化Top-down)

Early return是指的是在函式中，一旦找到答案時就提前結束函式的執行，其他的recursion要強制終止，不會再執行後續的程式碼，直接return result。

Early return的優點是在處理錯誤情況或一些預期的條件時，當滿足提前返回的條件時，Retuen改成True或False，可以避免多層的的條件判斷，使程式碼更加簡潔也增加了程式的可維護性可以優化程式碼。

以下是Early return的簡單範例，這一個函式用於計算a和b的和，但如果其中一個數字為負數，就直接返回0，不需要執行後續的加法的程式碼。

def add(a, b):
    if a < 0 or b < 0:
        return 0
    else:
        return a + b

若以leetcode的112. Path Sum來說

這是原本的Top-down寫法

用Early return去優化

Memoize(優化Bottom-up)

Memoize是指一種用於提高函式效能的方法，當一個函式的輸入資訊非常大或需要花費很長時間計算時，可以使用Memoize，在第一次計算後，先把計算結果儲存起來，若是之後有相同輸入的情況就直接返回儲存的結果，是一種去重複的概念，可以省去計算時間。

我們通常會用一個hash table(Dictionary）來儲存計算結果，key存的是所有參數的值，value存的是回傳值，當函式被呼叫時，會先檢查是否已經計算過該輸入的結果，如果是，就從hash table(Dictionary）中回傳結果(要改寫所有return部分)。這邊要注意的是，如果hash table中的key不是immutable的話，就不能用Memoize這個方法。另外要加上判斷式是否在hash table內(是否之前出現過)。

若以leetcode的509. Fibonacci Number來說

這是原本的Bottom-up寫法

用Memoize去優化

或是偷吃步用裝飾器@functools.lru_cache()

Bottom-up+裝飾器@functools.lru_cache()就是Memoize的寫法