The iron ML notebook
  • The iron data science notebook
  • ML & Data Science
    • Frequent Questions
      • Discriminative vs Generative models
      • Supervised vs Unsupervised learning
      • Batch vs Online Learning
      • Instance-based vs Model-based Learning
      • Bias-Variance Tradeoff
      • Probability vs Likelihood
      • Covariance vs Correlation Matrix
      • Precision vs Recall
      • How does a ROC curve work?
      • Ridge vs Lasso
      • Anomaly detection methods
      • How to deal with imbalanced datasets?
      • What is "Statistically Significant"?
      • Recommendation systems methods
    • Statistics
      • The basics
      • Distributions
      • Sampling
      • IQR
      • Z-score
      • F-statistic
      • Outliers
      • The bayesian basis
      • Statistic vs Parameter
      • Markov Monte Carlo Chain
    • ML Techniques
      • Pre-process
        • PCA
      • Loss functions
      • Regularization
      • Optimization
      • Metrics
        • Distance measures
      • Activation Functions
      • Selection functions
      • Feature Normalization
      • Cross-validation
      • Hyperparameter tuning
      • Ensemble methods
      • Hard negative mining
      • ML Serving
        • Quantization
        • Kernel Auto-Tuning
        • NVIDIA TensorRT vs ONNX Runtime
    • Machine Learning Algorithms
      • Supervised Learning
        • Support Vector Machines
        • Adaptative boosting
        • Gradient boosting
        • Regression algorithms
          • Linear Regression
          • Lasso regression
          • Multi Layer Perceptron
        • Classification algorithms
          • Perceptron
          • Logistic Regression
          • Multilayer Perceptron
          • kNN
          • Naive Bayes
          • Decision Trees
          • Random Forest
          • Gradient Boosted Trees
      • Unsupervised learning
        • Clustering
          • Clustering metrics
          • kMeans
          • Gaussian Mixture Model
          • Hierarchical clustering
          • DBSCAN
      • Cameras
        • Intrinsic and extrinsic parameters
    • Computer Vision
      • Object Detection
        • Two-Stage detectors
          • Traditional Detection Models
          • R-CNN
          • Fast R-CNN
          • Faster R-CNN
        • One-Stage detectors
          • YOLO
          • YOLO v2
          • YOLO v3
          • YOLOX
        • Techniques
          • NMS
          • ROI Pooling
        • Metrics
          • Objectness Score
          • Coco Metrics
          • IoU
      • MOT
        • SORT
        • Deep SORT
  • Related Topics
    • Intro
    • Python
      • Global Interpreter Lock (GIL)
      • Mutability
      • AsyncIO
    • SQL
    • Combinatorics
    • Data Engineering Questions
    • Distributed computation
      • About threads & processes
      • REST vs gRPC
  • Algorithms & data structures
    • Array
      • Online Stock Span
      • Two Sum
      • Best time to by and sell stock
      • Rank word combination
      • Largest subarray with zero sum
    • Binary
      • Sum of Two Integers
    • Tree
      • Maximum Depth of Binary Tree
      • Same Tree
      • Invert/Flip Binary Tree
      • Binary Tree Paths
      • Binary Tree Maximum Path Sum
    • Matrix
      • Set Matrix Zeroes
    • Linked List
      • Reverse Linked List
      • Detect Cycle
      • Merge Two Sorted Lists
      • Merge k Sorted Lists
    • String
      • Longest Substring Without Repeating Characters
      • Longest Repeating Character Replacement
      • Minimum Window Substring
    • Interval
    • Graph
    • Heap
    • Dynamic Programming
      • Fibonacci
      • Grid Traveler
      • Can Sum
      • How Sum
      • Best Sum
      • Can Construct
      • Count Construct
      • All Construct
      • Climbing Stairs
Powered by GitBook
On this page
  • Brute force
  • Memoization
  • Tubulation

Was this helpful?

  1. Algorithms & data structures
  2. Dynamic Programming

Grid Traveler

Brute force

def grid_traveler_brute_force(m: int, n: int) -> int:
    """
    Time complexity: O(2^(N+M))
        For each recursive call, we will make two calls (one for each type 
        of movement we are allowed to do). And, if we explore the height 
        of the recursive tree it will depend both in M and N. 
        Since we only can move towards one direction at every step, 
        the max height will depend on M+N.
    
    Space complexity: O(N+M)
        Since the max height is N+M, the max size of the stack will be 
        limited by it.
    """

    if m == 1 and n == 1:
        return 1
    elif m == 0 or n == 0:
        return 0
    
    return grid_traveler(m - 1, n) + grid_traveler(m, n - 1)

Memoization

def grid_traveler_dynamic(m: int, n: int, index: dict = {}) -> int:
    """
    Time complexity: O(N*M)
        M can take values { 0..M } and N can take values { 0..N }. 
        Hence there are N*M possible combination to be explored.

    Space complexity: O(N+M)
        The max height is N+M, hence the max size of the stack will be 
        limited by it.
    """

    if index is None:
        index = {}

    if (m,n) in index.keys():
        return index[(m,n)]
    if m == 1 and n == 1:
        return 1
    elif m == 0 or n == 0:
        return 0

    index[(m,n)] = (
        grid_traveler_dynamic(m - 1, n, index) + 
        grid_traveler_dynamic(m, n - 1, index)
    )

    index[(n,m)] = index[(m,n)]

    return index[(m,n)]

Tubulation

From down-right to top-left

def grid_traveler_tab(m: int, n: int) -> int:
    """
    Time complexity: O(N*M)
    
    Space complexity: O(N*M)

    6 3 1
    3 2 1
    1 1 1
    """

    table = [[0 for j in range(n)] for i in range(m)]
    table[-1][-1] = 1

    for i in range(m-1, -1, -1):  # right -> left
        for j in range(n-1, -1, -1):  # down -> up
            if (i + 1) < m:
                table[i][j] += table[i+1][j]
            if (j + 1) < n:
                table[i][j] += table[i][j+1]

    
    return table[0][0]

From top-left to down-right

def grid_traveler_tab(m: int, n: int):
    """
    Time complexity: O(N*M)
    
    Space complexity: O(N*M)
    """

    table = [[0 for j in range(n+1)] for i in range(m+1)]
    table[1][1] = 1
    # print(table)

    for i in range(m+1):  # left -> right
        for j in range(n+1):  # up -> down
            if i+1 <= m:
                table[i+1][j] += table[i][j]
            if j+1 <= n:
                table[i][j+1] += table[i][j]
    
    return table[-1][-1]
PreviousFibonacciNextCan Sum

Last updated 3 years ago

Was this helpful?