{%hackmd theme-dark %} # 300. (LIS)Longest Increasing Subsequence ###### tags: `fundamental` ## ChungYi * ## Solution 1 Recursive + Memorization =DP O(n^2) * ### Explanation F([1..n]) = Max{ lengthOfLISEndOfTail(i) for i= 1..n} lengthOfLISEndOfTail(i) = max( lengthOfLISEndOfTail( j ) for j= 1..i if nums[i] > nums[j] else 0, 1) DP for lengthOfLISEndOfTail(i) * ### performance o(n^2) * Complexity: o(n^2) * Performance * time: 65% * memeory 3

# Go helper functions ###### tags: `Tools`

# JAVA helper functions ###### tags: `Tools` Some frequently used helper functions: * Collections.binarySearch() * Collections.sort() * Arrays.binarySearch() * Arrays.sort()

# 437. Path Sum III > https://leetcode.com/problems/path-sum-iii/ ###### tags: `DFS` ## By Felicia Runtime: 3 ms, 99.95% Memory Usage: 36.8 MB, 100% Lang: Java Same concept as YuZhen's solution ``` Java class Solution { public int pathSum(TreeNode root, int sum) { Map<Integer, Integer> targetToPaths = new HashMap<>(); targetToPaths.put(0, 1); return findPaths(root, sum, 0, targetToPaths); } private int findPaths(TreeNode root, int target, int sum, Map<I