Maximum falling path sum (अधिकतम गिरते हुए पथ का योग)

आपके पास ऊँचाई h और चौड़ाई w वाला एक ग्रिड दिया गया है। इस ग्रिड में आपको ऊपर से नीचे की ओर बढ़ते हुए मिलने वाले पथों में से उस पथ का अधिकतम योग निकालना है, जिसमें प्रत्येक कदम पर आप नीचे की ओर मौजूद तीन आस-पास की कोशिकाओं में से किसी एक में जा सकते हैं। अर्थात्, यदि आप (r, c) स्थिति पर हैं, तो अगला कदम (r + 1, c - 1), (r + 1, c), या (r + 1, c + 1) पर होगा। इसे हम “falling sum” इसलिए कहते हैं, क्योंकि आप ग्रिड के शीर्ष से लेकर सबसे निचले छोर तक “गिरते हुए” आगे बढ़ते हैं। आपका कार्य इस पथ का अधिकतम योग ढूँढ़ना है।