Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Minimum path sum

    Given a grid of height h and width w filled with integers, you are asked to find a path from the top-left to the bottom-right corner that minimizes the sum of numbers along the path. You are only allowed to move right or down.
     
    3
    2
    1
    3
    1
    9
    2
    3
    9
    1
    5
    4

    Input

    The first line of the input contains two integers h and w (1 ≤ h, w ≤ 1000).
    The next h lines contain w space-separated integers representing the values in the grid .

    Output

    The program should print the minimum possible sum to get from the top-left corner to the bottom-right corner.

    Examples

    Input
    Output
    3 4 3 2 1 3 1 9 2 3 9 1 5 4
    15

    Explanation

    We can move: 3 → 2 → 1 → 2 → 3 → 4
     
    Hint 1
    The state in a dynamic programming problem can be a 2-dimensional array.
    Hint 2
    It can represent the best possible solution up to that coordinate (d[r][c] represents the best path to reach the row r and the column c).
     

    Why doesn’t the greedy approach work here? Imagine if you always moved in the direction of the smallest possible value. What would be the issue there?
     

    Constraints

    Time limit: 1.5 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue