Dynamic Programming

Definition Dynamic Programming is a very powerful programming paradigm that can be employed to find optimal solutions to problems that possess the following properties: overlapping subproblems and optimal substructure. Overlapping subproblems A problem can be decomposed into smaller subproblems than can be reused multiple time to construct the overall solution The solutions to subproblems are often memoized to avoid re-work and improve time complexity Solutions to subproblems are reused more than once by subsequent solutions Optimal substructure The optimal solution to a problem can be constructed from the optimal solution of overlapping subproblems....

January 23, 2023 · 2 min · 343 words · Me

Binary Tree: Postorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation left ➡️ right ➡️ root class Solution: def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 Post-order...: [3, 6, 9, 4, 1, 2, 0] T: O(N) S: O(N) worst case; O(log N) average """ if result is None: result = [] if not root: return [] self....

December 12, 2022 · 1 min · 174 words · Me

Binary Tree: Inorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation left ➡️ root ➡️ right class Solution: def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 In-order...: [3, 1, 6, 4, 9, 0, 2] T: O(N) S: O(N) worst case; O(log N) average """ if result is None: result = [] if not root: return [] self....

December 12, 2022 · 1 min · 187 words · Me

Binary Tree: Preorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation root ➡️ left ➡️ right class Solution: def traversal(self, root: 'TreeNode', ans=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 Pre-order...: [0, 1, 3, 4, 5, 9, 2] """ if not root: return [] if ans is None: ans = [] ans....

December 12, 2022 · 1 min · 151 words · Me