Minimum Falling Path Sum














































Minimum Falling Path Sum




Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

 

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:
  • [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
  • [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
  • [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.
Input Format:-
{{1,2,3},{4,5,6},{7,8,9}}(in main)
Output
Result 12
#include<bits/stdc++.h>
using namespace std;

int minFallingPathSum(vector<vector<int>>& A) {
int row=A.size();
if(row==0)return 0;
int col=A[0].size(),mini=INT_MAX;
vector<vector<int>>val(row,vector<int>(col,0));
for(int i=0;i<col;i++)val[0][i]=A[0][i];
for(int i=1;i<row;i++){
for(int j=0;j<col;j++){
int up=INT_MAX,left=INT_MAX,right=INT_MAX;
up=val[i-1][j];
if(j-1>=0)left=val[i-1][j-1];
if(j+1<col)right=val[i-1][j+1];
val[i][j]=min(up,min(left,right))+A[i][j];
}
}
for(int i=0;i<col;i++)
{
int z=val[row-1][i];
if(z<mini)mini=z;
}
return mini;
}

int main(){
vector<vector<int>>t={{1,2,3},{4,5,6},{7,8,9}};
int z=minFallingPathSum(t);
cout<<"Result "<<z<<endl;
return 0;
}

More Articles of Khitish Panigrahi:

Name Views Likes
Rotate Image 142 0
Edit Distance 88 1
Integer to Roman 117 2
Roman to Integer 107 2
Shortest Path Problem 111 2
Dijkstra 115 2
Hamiltonian Path 105 3
Travelling Salesman Problem 109 3
Hamiltonian Cycle 108 3
Number of Operations to Make Network Connected 104 2
Time Needed to Inform All Employees 101 2
Last Stone Weight II(any weight can be picked) 113 2
Last Stone Weight 119 2
Course Schedule II (print the order) 91 2
Course Schedule 103 2
0-1knapsack 116 2
Commutable Islands 224 2
Cheapest Flights Within K Stops 114 2
Friend Circles 99 2
Longest Palindromic Subsequence (Print Subsequence) 107 2
Longest Palindromic Subsequence (print only length) 98 2
longest palindromic substring(improved) 95 2
Longest Common Subsequence (Print the Subsequence) 98 2
Longest Common Subsequence (Print only Length) 100 2
Cycle in Undirected Graph 122 2
IOT SMART HOME 142 2
Working of Home Networks 100 2
Smart and Safe Cab Finder Algorithm 147 2
Minimum Falling Path Sum 175 3
Maximum Length of a Concatenated String with Unique Characters 100 3
Stack Pushing Game(Push Dominoes Game) 101 3
Boats to Save People 120 3
Find Single Non-repeated Number 96 3
Create Ranges 90 3
Triangle 95 3
Restore IP Addresses 100 4
Number of Matching Subsequences 89 3
Max Area of Island 101 3
Number of Islands 85 3
Is Subsequence 99 3
Word Break 98 3
Perfect Number 97 3
Longest Arithmetic Sequence 95 3
Container With Most Water 101 3
Maximal Square 95 3
Best Time to Buy and Sell Stock 100 3
Distance Between Bus Stops 97 3
Validate IP Address 110 3
Longest Mountain in Array 105 4
Sequential Digits 101 3
Path with Maximum Gold 112 3
House Robber with houses arranged in circular manner 127 3
Increasing Triplet Subsequence 110 5
4Sum 106 3
3Sum 97 3
ZigZag Conversion 133 4
House Robber 97 3
Minimum Path Sum 98 3
Unique Paths with obstacles 90 2
Find and Replace Pattern 100 3
Minimum Size Subarray Sum 97 3
Maximum Subarray 103 5
Find All Anagrams in a String 65 3
Permutation in String 66 3
Subarray Sum Equals K 102 3
Maximum Product Subarray 81 4
Permutation with duplicates 77 6
Subsets with duplicates 77 7
Partition Equal Subset Sum 69 5
Relative Sort Array 65 3
Permutations 67 4
Combination Sum 125 4
All combinations that add up to a given sum 69 3
Combinations 84 7
Palindrome Partitioning 70 3
Climbing Stairs 86 5
Fibonacci Number 83 5
Unique Paths 76 3
Longest Increasing Subsequence 66 8
Gas Station 75 7
Minimum number of Perfect square needed to form a number 60 7
Permutation Sequence 142 16
Coin Change 71 6
Multiple Word Searching Algorithm 78 8
Word Search 67 6
Valid Anagram 91 8
Remove Nth Node From End of List 90 6
Linked List Cycle 67 6
Implement strStr() 67 4
Odd Even Linked List 60 6
Valid Palindrome 64 4
Maximum Depth of Binary Tree 60 3
Binary Tree Zigzag Level Order Traversal 78 4
Kth Smallest Element in a BST 47 2
Evaluate Reverse Polish Notation 64 3
String to Integer (atoi) 82 4
Intersection of Two Linked Lists 69 3
Multiply Strings 70 5
Palindromic Substrings 59 4
Add Strings 56 2
Longest Substring Without Repeating Characters 63 4
Longest Palindromic Substring 62 2
Jump Game 68 3
Majority Element 59 2
Top K Frequent Elements 91 7
Factorial Trailing Zeroes 53 2
Excel Sheet Column Number 55 3
Find Peak Element 84 4
Merge Intervals 57 3
Letter Combinations of a Phone Number 69 4
Populating Next Right Pointers in Each Node 66 2
Invert Binary Tree 62 4
Swap Nodes in Pairs 60 5
3Sum Closest 56 2
Permutation Sequence 85 4
Letter Tile Possibilities 124 3
The k-th Lexicographical String of All Happy Strings of Length n 70 3
Children Sum Parent 129 5
Check if Binary Tree is BST 126 5
Delete Node in Linked List without a head pointer 96 2
Connect all siblings in a Binary Search Tree 86 2
Delete a node from BST in C++ 96 3

Comments