WhiteBox
DSA
Start coding DSA Beyond LeetCode System Design AI Engineering White Room
RoadmapProblem sets
Quizzes Dan Ladder Contests Templates Graph Editor
Guides Library
Login Sign up
Sign up Log in

Workspaces

Start coding DSA Beyond LeetCode System Design AI Engineering White Room

DSA

Overview Roadmap Problem sets Quizzes Dan Ladder Contests Templates Graph Editor CP Guessr

Library

Library Guides

Community

Leaderboard Contributors Refer & Earn Cosmetics

Tools

Resume Reviewer Job Boards Changelog

Dynamic programming 0/49

DSA 0 of 360 problems solved
0%
Overview

Curriculum

    1. DP fundamentals 0/31
    2. Knapsack DP 0/18
      1. Grid DP 0/9
      2. Knapsack 0/9
  1. DSA
  2. / Dynamic programming

Knapsack DP: capacity tables and grid paths · 1 of 2

Grid DP

Count the paths through a grid, find the cheapest path and the largest square of 1s, with one state per cell and a transition from the neighbouring cells.

3,023 words · 14 min read

Lesson Problems9 Reading6

Books1

  • Competitive Programmer’s Handbook, Chapter 7: Dynamic programming Section 7.3: the largest-sum path through a grid moving right and down, with its table and code. (opens in a new tab)

Links2

  • usaco.guide Paths on Grids Counting paths with blocked cells on CSES Grid Paths, then the longest common subsequence as a path through a grid. usaco.guide (opens in a new tab)
  • atcoder.jp Grid 1 The blocked-cell count of this lesson on a grid of up to 1,000 rows and 1,000 columns, with the answer modulo 10^9 + 7. atcoder.jp (opens in a new tab)

More links3

  • Introduction to DP — USACO Guideusaco.guide (opens in a new tab)
  • Grid DP Introductionalgo.monster (opens in a new tab)
  • Introduction to Dynamic Programming — CP-Algorithmscp-algorithms.com (opens in a new tab)
Lesson: Grid DP
Overview Roadmap Problem sets Log in