DSA Master Logo
DSAMaster
Sign InSign Up
easyDynamic ProgrammingPattern: DP

Maximum Collectible Points in Grid with K Moves Solution

Problem Statement

You are given a 2D integer array `grid` of dimensions `m x n`, where `grid[r][c]` represents the points available at cell `(r, c)`. You are also given an integer `k`, representing the maximum number of moves allowed. From any cell `(r, c)`, you can move to an adjacent cell `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, or `(r, c-1)`, provided the adjacent cell is within the grid boundaries. You can start from any cell `(r, c)` in the grid. Your task is to find the maximum total points that can be collected starting from any cell and making at most `k` moves. Points are collected when a cell is entered. If a cell is visited multiple times, its points are collected each time.

Examples

Example 1:
Input:grid = [[1, 2], [3, 4]], k = 1
Output:7
Explanation: Starting at cell (1,0) with value 3, move to (1,1) with value 4. Total points collected: 3 + 4 = 7. (1 move)
Example 2:
Input:grid = [[10, 1], [1, 100]], k = 0
Output:100
Explanation: With 0 moves, you can only collect points from your starting cell. The maximum value in the grid is 100 (at cell (1,1)).

Constraints

  • `1 <= m, n <= 50`
  • `0 <= k <= 100`
  • `-1000 <= grid[i][j] <= 1000`
Time: O(k * m * n) Space: O(k * m * n)
This problem can be efficiently solved using dynamic programming. Define `dp[moves][r][c]` as the maximum points collectible by making exactly `moves` steps and ending at cell `(r, c)`. Initialize `dp[0][r][c]` with `grid[r][c]` for all `(r,c)`. Then, for `m` from 1 to `k`, update `dp[m][r][c]` by considering `grid[r][c]` plus the maximum points achievable from an adjacent cell `(prev_r, prev_c)` in `m-1` moves. The final answer is the maximum value across all `dp[m][r][c]` for `0 <= m <= k` and all `(r,c)`.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import sys\n\ndef main():\n input = sys.stdin.readline\n\n m, n = map(int, input().split())\n grid = []\n for _ in range(m):\n grid.append(list(map(int, input().split())))\n k = int(input())\n\n # DP state: prev_dp[r][c] represents the maximum points collected\n # after 's-1' moves, ending at cell (r, c).\n # current_dp[r][c] represents the maximum points collected\n # after 's' moves, ending at cell (r, c).\n # We use two layers for space optimization.\n\n # Initialize prev_dp for s = 0 moves\n prev_dp = [[0] * n for _ in range(m)]\n max_overall_points = 0\n\n # Base case: s = 0 moves\n # If k = 0, we can only start at any cell and collect its points.\n # max_overall_points tracks the maximum value across all dp states.\n for r in range(m):\n for c in range(n):\n prev_dp[r][c] = grid[r][c]\n max_overall_points = max(max_overall_points, prev_dp[r][c])\n\n dr = [-1, 1, 0, 0]\n dc = [0, 0, -1, 1]\n\n # Iterate for s from 1 to k moves\n for s in range(1, k + 1):\n current_dp = [[0] * n for _ in range(m)]\n for r in range(m):\n for c in range(n):\n max_points_from_prev_step_neighbors = 0\n # Check all adjacent cells (nr, nc)\n for i in range(4):\n nr, nc = r + dr[i], c + dc[i]\n\n # Check if (nr, nc) is within grid boundaries\n if 0 <= nr < m and 0 <= nc < n:\n max_points_from_prev_step_neighbors = max(\n max_points_from_prev_step_neighbors,\n prev_dp[nr][nc]\n )\n \n # Current cell's points + max points from a neighbor in the previous step\n current_dp[r][c] = grid[r][c] + max_points_from_prev_step_neighbors\n max_overall_points = max(max_overall_points, current_dp[r][c])\n \n prev_dp = current_dp # Update prev_dp for the next iteration\n\n sys.stdout.write(str(max_overall_points) + '\n')\n\nif __name__ == '__main__':\n main()\n

Related Problems

Maximum Profit from Scheduled Deliveries
Dynamic Programming•medium
Longest Alternating Subsequence
Dynamic Programming•medium
Max Resource Allocation
Dynamic Programming•easy
Maximize Subset Points
Dynamic Programming•medium