Ninja and his Friends (3D DP)
2D/3D DP and Grids DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Maximum chocolates collected by two friends moving through a matrix with overlapping paths, Dynamic Programming, Memoization, Tabulation, Space Optimization, Grid Traversal, Two-dimensional Array Traversal, Recursion, Time Complexity, Space Complexity, Matrices, dynamic programming, memoization, tabulation, space optimization, recursion, Dynamic Programming (DP).
Maximum Chocolates Collected We are given an N x M matrix, where each cell mat[i][j] contains a certain number of chocolates. Two friends, Alice and Bob, start at the top row. Alice begins at cell (0, 0) and Bob at cell (0, M 1). They can only move to cells directly below them in three directions: straight down (↓), down right (↘), or down left (↙). When Alice and Bob visit a cell, they collect all the chocolates from that cell. If both Alice and Bob visit the same cell, the chocolates from that cell are counted only once. They cannot move outside the boundaries of the given matrix. Your task is to find the maximum total number of chocolates that Alice and Bob can collect together. Input Specification The first line contains two integers N and M, representing the number of rows and columns of the matrix, respectively. Following N lines each contain M integers, representing the chocolate counts in each cell mat[i][j]. Output Specification Return a single integer, the maximum number of chocolates that Alice and Bob can collect. Constraints 1 <= N, M <= 70 0 <= mat[i][j] <= 100 Sample Test Case Input: Output: