easyDynamic ProgrammingPattern: DP
Minimum Product Path in Grid Solution
Problem Statement
Given an `m x n` grid, `grid`, where each cell `(i, j)` contains a positive floating-point number. You are to find a path from the top-left cell `(0, 0)` to the bottom-right cell `(m-1, n-1)`. At each step, you can only move either right or down. The 'cost' of a path is defined as the product of all numbers in the cells visited along that path. Your task is to return the minimum possible product among all valid paths.
Examples
Example 1:
Input:grid = [[0.1, 0.5], [0.3, 0.2]]
Output:0.006
Explanation: Path (0,0) -> (1,0) -> (1,1) multiplies to 0.1 * 0.3 * 0.2 = 0.006. Path (0,0) -> (0,1) -> (1,1) multiplies to 0.1 * 0.5 * 0.2 = 0.01. The minimum is 0.006.
Example 2:
Input:grid = [[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]]
Output:324.0
Explanation: The path (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) results in 1.0 * 2.0 * 3.0 * 6.0 * 9.0 = 324.0. This is the minimum product.
Constraints
- 1 <= m, n <= 100
- 0.0 < grid[i][j] <= 100.0 (all values are positive)
- The answer is guaranteed to fit within a standard double-precision floating-point type.
Time: O(m*n) Space: O(m*n)
This problem can be efficiently solved using dynamic programming. We define `dp[i][j]` as the minimum product to reach cell `(i, j)`. The recurrence relation is `dp[i][j] = grid[i][j] * min(dp[i-1][j], dp[i][j-1])`, with appropriate base cases for the first row and column. The final answer is `dp[m-1][n-1]`. This approach avoids recomputing subproblems.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def solve():
lines = sys.stdin.readlines()
line_idx = 0
m, n = map(int, lines[line_idx].split())
line_idx += 1
grid = []
for _ in range(m):
grid.append(list(map(float, lines[line_idx].split())))
line_idx += 1
# dp[i][j] stores the minimum product to reach cell (i, j)
dp = [[0.0] * n for _ in range(m)]
# Base case: The product to reach (0, 0) is just the value in (0, 0)
dp[0][0] = grid[0][0]
# Fill the first row: only way to reach (0, j) is from (0, j-1)
for j in range(1, n):
dp[0][j] = dp[0][j - 1] * grid[0][j]
# Fill the first column: only way to reach (i, 0) is from (i-1, 0)
for i in range(1, m):
dp[i][0] = dp[i - 1][0] * grid[i][0]
# Fill the rest of the grid
# For any cell (i, j), we can reach it either from (i-1, j) (move down)
# or from (i, j-1) (move right). Since all numbers are positive,
# we just take the minimum of the products from the two possible previous cells.
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) * grid[i][j]
# The result is the minimum product to reach the bottom-right cell (m-1, n-1)
print(dp[m - 1][n - 1])
solve()