Grids पर DP

Grids पर DP एक city grid में चलने के तरीके count करने या एक corner से दूसरे तक सबसे सस्ता path ढूंढने जैसा है, nearby squares के answers उपयोग करते हुए।

In this page:

Grid DP Idea
State
Transition
Minimum Path Sum
Practice

Syntax

markup

for r in range(rows):
    for c in range(cols):
        if r == 0 and c == 0:
            dp[r][c] = base_value
        else:
            from_top = dp[r - 1][c] if r > 0 else 0
            from_left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = from_top + from_left

Grid DP Idea

Grid DP problems एक 2D grid में paths के बारे में कुछ पूछती हैं — किसी cell तक पहुंचने के तरीकों की संख्या, या इसका सबसे सस्ता path — और इसे हर cell के लिए एक answer भरकर solve करती हैं इस आधार पर कि कौन सी cells इस तक पहुंच सकती हैं।

उदाहरण: Grid DP Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Grid DP: fill in an answer for every cell based on the cells that can reach it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Grid DP: fill in an answer for every cell based on the cells that can reach it");
	}
}

print("Grid DP: fill in an answer for every cell based on the cells that can reach it")

#include <stdio.h>
int main() {
	printf("Grid DP: fill in an answer for every cell based on the cells that can reach it");
	return 0;
}

State

dp[r][c] row r, column c पर cell का answer store करता है, इसलिए dp values की grid original grid की shape को mirror करती है, हर cell का answer पहले compute की गई cells से बनते हुए।

उदाहरण: State

#include <iostream>
using namespace std;
int main() {
	int dp[3][3] = {0};
	cout << "dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[3][3];
		System.out.println("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape");
	}
}

dp = [[0]*3 for _ in range(3)]
print("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape")

#include <stdio.h>
int main() {
	int dp[3][3] = {0};
	printf("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape");
	return 0;
}

Transition

जब movement right और down तक restricted हो, एक cell सिर्फ इसके बिल्कुल ऊपर वाली cell या बिल्कुल बाईं cell से पहुंचा जा सकता है, इसलिए dp[r][c] आमतौर पर dp[r-1][c] और dp[r][c-1] को problem जिस भी तरीके से मांगे उस तरह combine करके बनता है (paths count करने के लिए sum, सबसे सस्ते path के लिए minimum)।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	int dp[3][3] = {0};
	dp[0][0] = 1;
	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++) {
			if (r > 0) dp[r][c] += dp[r-1][c];
			if (c > 0) dp[r][c] += dp[r][c-1];
		}
	cout << "Paths to bottom-right (right/down moves only): " << dp[2][2];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[3][3];
		dp[0][0] = 1;
		for (int r = 0; r < 3; r++)
			for (int c = 0; c < 3; c++) {
				if (r > 0) dp[r][c] += dp[r-1][c];
				if (c > 0) dp[r][c] += dp[r][c-1];
			}
		System.out.println("Paths to bottom-right (right/down moves only): " + dp[2][2]);
	}
}

dp = [[0]*3 for _ in range(3)]
dp[0][0] = 1
for r in range(3):
    for c in range(3):
        if r > 0: dp[r][c] += dp[r-1][c]
        if c > 0: dp[r][c] += dp[r][c-1]
print("Paths to bottom-right (right/down moves only):", dp[2][2])

#include <stdio.h>
int main() {
	int dp[3][3] = {0};
	dp[0][0] = 1;
	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++) {
			if (r > 0) dp[r][c] += dp[r-1][c];
			if (c > 0) dp[r][c] += dp[r][c-1];
		}
	printf("Paths to bottom-right (right/down moves only): %d", dp[2][2]);
	return 0;
}

Minimum Path Sum

एक minimum path sum problem के लिए, dp[r][c] cell की अपनी cost plus top या left neighbor में से जिसकी accumulated cost अब तक छोटी हो उसके बराबर है, सबसे सस्ते route को एक समय में एक cell आगे propagate करते हुए।

उदाहरण: Minimum Path Sum

#include <iostream>
using namespace std;
int main() {
	int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
	int dp[3][3];
	dp[0][0] = grid[0][0];
	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++) {
			if (r==0 && c==0) continue;
			int top = r>0 ? dp[r-1][c] : 1000000;
			int left = c>0 ? dp[r][c-1] : 1000000;
			dp[r][c] = grid[r][c] + min(top, left);
		}
	cout << "Minimum path sum: " << dp[2][2];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
		int[][] dp = new int[3][3];
		dp[0][0] = grid[0][0];
		for (int r = 0; r < 3; r++)
			for (int c = 0; c < 3; c++) {
				if (r==0 && c==0) continue;
				int top = r>0 ? dp[r-1][c] : 1000000;
				int left = c>0 ? dp[r][c-1] : 1000000;
				dp[r][c] = grid[r][c] + Math.min(top, left);
			}
		System.out.println("Minimum path sum: " + dp[2][2]);
	}
}

grid = [[1,3,1],[1,5,1],[4,2,1]]
dp = [[0]*3 for _ in range(3)]
dp[0][0] = grid[0][0]
for r in range(3):
    for c in range(3):
        if r == 0 and c == 0:
            continue
        top = dp[r-1][c] if r > 0 else float('inf')
        left = dp[r][c-1] if c > 0 else float('inf')
        dp[r][c] = grid[r][c] + min(top, left)
print("Minimum path sum:", dp[2][2])

#include <stdio.h>
int main() {
	int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
	int dp[3][3];
	dp[0][0] = grid[0][0];
	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++) {
			if (r==0 && c==0) continue;
			int top = r>0 ? dp[r-1][c] : 1000000;
			int left = c>0 ? dp[r][c-1] : 1000000;
			dp[r][c] = grid[r][c] + (top < left ? top : left);
		}
	printf("Minimum path sum: %d", dp[2][2]);
	return 0;
}

Practice

यह pattern obstacles वाली grids तक naturally extend होता है (blocked cells बस zero ways या infinite cost contribute करती हैं) और robot navigation जैसी constrained movement problems model करने का एक आम तरीका है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation");
	}
}

print("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation")

#include <stdio.h>
int main() {
	printf("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Matrix Chain Multiplication Next Lesson → DP on Trees