KEMBAR78
DP Patterns | PDF | Top Down And Bottom Up Design | Algorithms
Scribd
Upload
103 views10 pages

DP Patterns

The document discusses finding the maximum or minimum cost path to reach a target node in a dynamic programming problem. It explains that the problem involves finding the optimal path from a source node to a target node by moving between nodes that have associated costs. It provides the recurrence relation to calculate the maximum or minimum cost to reach each node based on the costs of paths from previous nodes. It also describes how to approach the problem using both top-down memoization and bottom-up tabulation dynamic programming approaches.

Uploaded by

NetriderTheThechie
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
103 views10 pages

DP Patterns

The document discusses finding the maximum or minimum cost path to reach a target node in a dynamic programming problem. It explains that the problem involves finding the optimal path from a source node to a target node by moving between nodes that have associated costs. It provides the recurrence relation to calculate the maximum or minimum cost to reach each node based on the costs of paths from previous nodes. It also describes how to approach the problem using both top-down memoization and bottom-up tabulation dynamic programming approaches.

Uploaded by

NetriderTheThechie
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
You are on page 1/ 10

Pt #1

Different

Patterns You

Must Know In

Dynamic

Programming
Max(Min) Path to

#1
Reach a Target

Statement goes like...

Find max(min) cost to reach a target node

Problem Breakdown

Consider you start from 0 (source) and you need to

reach t (target)

Nodes between 0 and t are ...

0 1 2 3 ......... t-3 t-2 t-1 t


Max(Min) Path to

#2
Reach a Target

Problem Breakdown
Nodes between 0 and t are ...

0 1 2 3 ......... t-3 t-2 t-1 t

Depending on problem you may either jump or skip few

node or even cross one node after another

Every node has a cost associated with it which you add if

you cross that node

Many a times problem requires you to find a max (min)

cost in a grid so obviously you can't consider all the cells

for your path only choose nodes connecting source and

target with max (min) cost


Max(Min) Path to

#3
Reach a Target

Getting the recurrence relation

Nodes between 0 and t are ...

0 1 2 3 ......... t-3 t-2 t-1 t

Make a function getMaxCost(int t) which just returns

max cost from 0 (soure) to t

Consider from previous k nodes there is a direct path to t

(need to be figured from problem statement)


getMaxCost(t) = max(getMaxCost(t-1), getMaxCost(t-2),
...getMaxCost(t-k)) + cost[t]

This is your recurrence relation


Max(Min) Path to

#4
Reach a Target

Recursive solution
Max(Min) Path to

#5
Reach a Target

How to use DP here ?

int getMaxCost(int t, int[] cost, int k);


In above recursive function values for cost and k

are constant only value of t is changing (1D dp)

For any t if you see getMaxCost(t, cost, k) being

called multiple times so it's better to call it only

once and store the result to avoid further callings

thus reducing the time

recursion => memoised DP => tabulated DP


recursion => Top-Down => Bottom-Up
Max(Min) Path to

#6 Reach a Target
Top-Down or memoized DP (syntax)
Max(Min) Path to

#7
Reach a Target
Bottom-Up (syntax)
Max(Min) Path to

#8
Reach a Target

Problems(Leetcode) to practice

Minimum Path Sum


Minimum Falling Path Sum
Perfect Squares
Coin Change
Triangle
One and Zeroes
Dungeon Games
Minimum Number of Refueling Stops
Mayank
Software Engineer | StoryTeller

Code

Smarter
I hope you found it useful

Follow for content related to DSA

You might also like