Minimum Path Sum
Learn Minimum Path Sum (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Minimizing the Sum Along a Path Same grid-DP framework as Unique Paths, with the combine operation changed from SUM to MIN: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) - each cell picks whichever of "from above" or "from left" gives the cheaper running total.
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Longest Common Substring
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Burst Balloons
- Optimal BST
- Diameter (Tree DP)
- Maximum Path Sum (Tree DP)
- Tree Independent Set
- Traveling Salesman Problem
- Assignment Problems
- Counting Numbers (Digit DP)
- Digit Constraints