Scribd
Upload
7 views2 pages

Treasure Grid Game: DP Optimization Guide

The document outlines a mini project assignment focused on the Treasure Grid Game, which involves using Dynamic Programming to find the minimum cost path in a grid. It includes tasks for theoretical analysis, coding implementation, and an optional extension challenge, along with submission guidelines and evaluation criteria. The project aims to enhance understanding of DP concepts, recurrence relations, and practical coding skills.

Uploaded by

Niloy Mahmud
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Treasure Grid Game: DP Optimization Guide

The document outlines a mini project assignment focused on the Treasure Grid Game, which involves using Dynamic Programming to find the minimum cost path in a grid. It includes tasks for theoretical analysis, coding implementation, and an optional extension challenge, along with submission guidelines and evaluation criteria. The project aims to enhance understanding of DP concepts, recurrence relations, and practical coding skills.

Uploaded by

Niloy Mahmud
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Mini Project Assignment: The Treasure Grid Game

Learning Objectives
• Understand how Dynamic Programming (DP) can solve optimization problems on grids.
• Learn to define states, recurrence relations, and base cases.
• Compare theoretical DP analysis with practical coding implementation.

Game Story
You are trapped inside a dungeon represented as an N × M grid.
• Each cell (i, j) contains a non-negative cost (e.g., energy required to move through).
• You start at the top-left corner (0, 0) and want to reach the bottom-right corner (N −1, M −1).
• You must minimize the total cost of the journey.

Rules
1. At each step, you may move only DOWN or RIGHT.
2. You must accumulate the costs of the cells you step on (including start and end).

Tasks
Part A: Theoretical Analysis
1. Formulate the recurrence relation for the minimum-cost path.
• Define DP state clearly (e.g., dp[i][j] = ?).
• State the base cases.
2. Draw a DP table for the following test grid (show values filled step by step):
 
1 3 5
Grid A (3x3): 2 1 2
4 3 1

Expected answer: Minimum cost path = 7 (path: 1 → 2 → 1 → 2 → 1).


3. Analyze the time and space complexity of your recurrence.

Part B: Coding Implementation


1. Implement the DP solution in Python / C++ / Java.
2. Run your code on the following grid:
 
1 3 1 2 9
2 1 4 2 7
 
3
Grid B (5x5):  2 1 3 6
8 3 2 1 5
3 6 7 2 1

Expected minimum cost = 12.

1
3. Output both:
• The minimum cost value.
• The path taken (sequence of coordinates or values).

Part C: Extension Challenge (Optional Bonus)


Modify the rules:
• Now you may move in all four directions (up, down, left, right).

• You cannot revisit a cell.


Tasks:
• Propose a modified DP state definition.

• Explain why this problem is more complex than the down-right version.
• Implement if you can (hint: requires memoization with visited states).

Submission Guidelines
• Submit a short report (3–5 pages) including:
– Recurrence relation and explanation.
– Completed DP table for Grid A.
– Complexity analysis.
– Screenshots of program output for Grid B.
• Submit source code separately.

Evaluation (20 marks total)


• Recurrence relation & DP formulation – 5 marks
• Manual DP table computation (Grid A) – 3 marks
• Correct code implementation (Grid B) – 6 marks

• Complexity analysis – 3 marks


• Report quality & clarity – 3 marks

You might also like