LeetCode #741: Cherry Pickup, Two Walkers DP for the Round Trip

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: in an N×N grid, each cell is empty (0), a cherry (1) or a thorn (−1). Go from the top-left to the bottom-right moving only right or down, then come back moving only left or up, and collect as many cherries as you can. Each cherry can be picked once. Brute force: take the best path there, then the best path back. This greedy approach can miss the best total. The key insight: the trip back is just a second path from the top-left. Move both walkers at the same time, one step each, so after t steps both have r + c = t. dp[t][r1][r2] is the most cherries when walker 1 is in row r1 and walker 2 is in row r2. There are four possible previous states. If both walkers are on the same cell, count its cherry once. If either one is on a thorn, the state is invalid. Dry run: in 0 1 −1 / 1 0 −1 / 1 1 1, the trip there picks up 4 and the trip back picks up 1, so the answer is 5. Complexity: O(N³) time and O(N²) space with rolling layers. Problem: https://leetcode.com/problems/cherry-... Related: Cherry Pickup II (1463), Minimum Path Sum (64), Unique Paths II (63) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode741 #cherrypickup #dynamicprogramming #dp #matrix #grid #hard #coding #codinginterview #dsa #python #google #faang #brutetobest