1 of 171

Design and Analysis of Algorithms
Course : Dr.Manoj Chandak Coordinator	Student Name : Antara Kawathekar Roll No : 16 Class : A1 Branch : Computer Science and engineering

2 of 171

Table of Content:

Longest Increasing Subsequence
Longest Divisible Subset
Multistage Graph Algorithm
Minimum Path Sum In a Grid

3 of 171

Longest Increasing Subsequence Using Dynamic Programming

Problem Statement:

Given an array of integers, the task is to find the length of the longest subsequence such that all elements of the subsequence are in strictly increasing order. A subsequence is a sequence that can be derived from the original array by deleting some or no elements without changing the order of the remaining elements.

The subsequence elements must appear in the same relative order as in the input array.
The subsequence is not necessarily contiguous.
We want the subsequence of the longest possible length.

Example :

for the array: [2,3,1] , the subsequences will be [{2},{3},{1},{2,3},{2,3,1}} but

{3,2} is not a subsequence because its elements are not in the same order as the original array.

And longest sequence is {2,3} with length 2

4 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	1	1	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(0 > 1) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

Example:

prev Array	-1	-1	-1	-1	-1
Index	0	1	2	3	4

maxLength=0

lastIndex=-1

5 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	(1) 2	1	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(2> 1) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

prev Array	-1	-1	(-1) 0	-1	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 0) ?

True

maxLength=dp[i]

maxLength=2

lastIndex=i

lastIndex=2

6 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	1	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(2 > 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 2) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

prev Array	-1	-1	0	-1	-1
Index	0	1	2	3	4

7 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	(1) 2	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(4 > 1) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

prev Array	-1	-1	0	(-1) 0	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[j]=0

4. Is dp[i] > maxLength ?

(2 > 2)?

False

8 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	2	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(4 > 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 2) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

prev Array	-1	-1	0	0	-1
Index	0	1	2	3	4

9 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	(2) 3	1
Index	0	1	2	3	4

Is num[i] > num[j] ?

(4 > 2) ?

True

Is dp[j]+1 > dp[i] ?

(3 > 2) ?

True

prev Array	-1	-1	0	(0) 2	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=3

prev[i]=j

prev[i]=2

4. Is dp[i] > maxLength ?

(3 > 2) ?

True

maxLength=dp[i]

maxLength=3

lastIndex=i

lastIndex=3

10 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	3	(1) 2
Index	0	1	2	3	4

Is num[i] > num[j] ?

(3 > 1) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

prev Array	-1	-1	0	2	(-1) 0
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 3) ?

False

11 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	3	2
Index	0	1	2	3	4

Is num[i] > num[j] ?

(3 > 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 2) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

prev Array	-1	-1	0	2	0
Index	0	1	2	3	4

12 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	3	(2) 3
Index	0	1	2	3	4

Is num[i] > num[j] ?

(3 > 2) ?

True

Is dp[j]+1 > dp[i] ?

(3 > 2) ?

True

prev Array	-1	-1	0	2	(0) 2
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=3

prev[i]=j

prev[i]=2

4. Is dp[i] > maxLength ?

(3 > 3) ?

False

13 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

j

i

dp Array	1	1	2	3	3
Index	0	1	2	3	4

Is num[i] > num[j] ?

(3 > 4) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

prev Array	-1	-1	0	2	2
Index	0	1	2	3	4

14 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

prev Array	-1	-1	0	2	2
Index	0	1	2	3	4

Is lastIndex !=-1?

(3 !=-1 )

True:

Add num[lastIndex] (4) at first position

lastIndex=prev[lastIndex]

lastIndex=2

4

Linked list

lis

15 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

prev Array	-1	-1	0	2	2
Index	0	1	2	3	4

Is lastIndex !=-1?

(2 !=-1 )

True:

Add num[lastIndex] (2) at first position

lastIndex=prev[lastIndex]

lastIndex=0

2

Linked list

lis

4

16 of 171

num Array	1	0	2	4	3
Index	0	1	2	3	4

prev Array	-1	-1	0	2	2
Index	0	1	2	3	4

Is lastIndex !=-1?

(0 !=-1 )

True:

Add num[lastIndex] (1) at first position

lastIndex=prev[lastIndex]

lastIndex=-1

In next iteration condition will fail and we have final inked list

2

Linked list

lis

4

1

17 of 171

Algorithm :

Step 1 : Input numbers in num array

Step 2 : Initialize dp array (size num length) with 1 and prev array (size num length) with -1

Step 3 : set maxlength :=0

lastIndex :=-1

Step 4 : for i := 1 to num length :

for j := 0 to i :

If num[i] > num[j] and dp[j]+1 > dp[i] :

dp[i]=dp[j]+1

prev[i]=j

If dp[i] > maxLength :

maxLength=dp[i]

lastIndex=i

18 of 171

Step 5 : Create a linked list lis

Step 6 : while lastIndex != -1 :

Add num[lastIndex] to the first position of lis

lastIndex = prev[lastIndex]

Step 7 : return lis

Note : Length of lis will give you length of longest increasing subsequence

prev array is not required if we only need length ( maxLength variable have it )

We need prev array for reconstruction of subsequence

19 of 171

Code ( In Java ) :

20 of 171

Code ( In Java ) :

21 of 171

Code ( In Java ) :

22 of 171

Few More Test Cases :

23 of 171

Analysis :

Space Complexity :

Input : array requires O(n) space
Dp array requires O(n) space
Prev Array requires O(n) space
Total: O( n+n+n ) = O( 3n ) = O(n)

Time Complexity :

For each index i ,we check all previous elements using j which results in n(n-1)/2 comparisons
Hence, time complexity is O(n²)

24 of 171

Wait there is an better option!

Patience Sorting (Greedy + Binary search approach) has better time complexity ( O(nlogn) ) than the Dynamic programming approach ( O(n²) )

To know more : Click here

25 of 171

Longest Divisible Subset

First of all let us understand the difference between subset and subsequence

Subset :

A subset is any combination of elements taken from a set or array, regardless of order or position.
Elements in a subset are not required to keep their original ordering from the array.

Subsequence :

A subsequence is derived by removing some or no elements from the array without changing the order of the remaining elements.
Elements in a subsequence must appear in the same relative order as in the original array, though they do not have to be contiguous.

Example : for [2,3,1] array

{1,2} is valid subset but not a valid subsequence

26 of 171

Longest Divisible Subset

Problem Statement :

Given an array of integers (num), find the largest subset such that a,b ∈ num, for every pair (a,b) either a%b=0 or b%a=0

As this is a subset, order does not matter
Subset must be with the longest possible length
In case of multiple subsets only one can be printed

Example: {1,10,5,7}

So longest subset possible is {1,5,10}

27 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	(1) 2	1	1	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(4 % 2 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

Example: Consider array [4,2,8,20,16]

prev Array	-1	(-1) 0	-1	-1	-1
Index	0	1	2	3	4

maxLength=0

lastIndex=-1

First sort num array

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 0) ?

True

maxLength=dp[i]

maxLength=2

lastIndex=i

lastIndex=1

28 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	(1) 2	1	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(8 % 2 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

prev Array	-1	0	(-1) 0	-1	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 2) ?

False

29 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	(1) 2	1	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(8 % 4 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(3 > 2) ?

True

prev Array	-1	0	(0) 1	-1	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=3

prev[i]=j

prev[i]=1

4. Is dp[i] > maxLength ?

(3 > 2) ?

True

maxLength=dp[i]

maxLength=3

lastIndex=i

lastIndex=2

30 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	(1) 2	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(16 % 2 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

prev Array	-1	0	1	(-1) 0	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 3) ?

False

31 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	(2) 3	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(16 % 4 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(3 > 2) ?

True

prev Array	-1	0	1	(0) 1	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=3

prev[i]=j

prev[i]=1

4. Is dp[i] > maxLength ?

(3 > 3) ?

False

32 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	(3) 4	1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(16 % 8 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(4 > 3) ?

True

prev Array	-1	0	1	(1) 2	-1
Index	0	1	2	3	4

3. dp[i]=dp[j]+1

dp[i]=4

prev[i]=j

prev[i]=2

4. Is dp[i] > maxLength ?

(4 > 3) ?

True

maxLength=dp[i]

maxLength=4

lastIndex=i

lastIndex=3

33 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	4	(1) 2
Index	0	1	2	3	4

prev Array	-1	0	1	2	(-1) 0
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(20 % 2 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(2 > 1) ?

True

3. dp[i]=dp[j]+1

dp[i]=2

prev[i]=j

prev[i]=0

4. Is dp[i] > maxLength ?

(2 > 4) ?

False

34 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	4	(2) 3
Index	0	1	2	3	4

prev Array	-1	0	1	2	(0) 1
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(20 % 4 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(3 > 2) ?

True

3. dp[i]=dp[j]+1

dp[i]=3

prev[i]=j

prev[i]=1

4. Is dp[i] > maxLength ?

(3 > 4) ?

False

35 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	4	(3) 4
Index	0	1	2	3	4

prev Array	-1	0	1	2	(1) 2
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(20 % 8 == 0) ?

True

Is dp[j]+1 > dp[i] ?

(4 > 3) ?

True

3. dp[i]=dp[j]+1

dp[i]=4

prev[i]=j

prev[i]=2

4. Is dp[i] > maxLength ?

(4 > 4) ?

False

36 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

j

i

dp Array	1	2	3	4	4
Index	0	1	2	3	4

Is num[i] % num[j] == 0 ?

(20 % 16 == 0) ?

False

No change in dp array and prev array

No change in maxLength and lastIndex

prev Array	-1	0	1	2	2
Index	0	1	2	3	4

37 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

Is lastIndex !=-1?

(3 !=-1 )

True:

Add num[lastIndex] (16) at first position

lastIndex=prev[lastIndex]

lastIndex=2

prev Array	-1	0	1	2	-1
Index	0	1	2	3	4

16

Linked list

lis

38 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

Is lastIndex !=-1?

(2 !=-1 )

True:

Add num[lastIndex] (8) at first position

lastIndex=prev[lastIndex]

lastIndex=1

prev Array	-1	0	1	2	-1
Index	0	1	2	3	4

Linked list

lis

8

16

39 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

Is lastIndex !=-1?

(1 !=-1 )

True:

Add num[lastIndex] (4) at first position

lastIndex=prev[lastIndex]

lastIndex=0

prev Array	-1	0	1	2	-1
Index	0	1	2	3	4

Linked list

lis

8

16

4

40 of 171

num Array	2	4	8	16	20
Index	0	1	2	3	4

Is lastIndex !=-1?

(0 !=-1 )

True:

Add num[lastIndex] (2) at first position

lastIndex=prev[lastIndex]

lastIndex=-1

prev Array	-1	0	1	2	-1
Index	0	1	2	3	4

Linked list

lis

8

16

4

2

41 of 171

Algorithm :

Step 1 : Input numbers in num array

Step 2 : Initialize dp array (size num length) with 1 and prev array (size num length) with -1

Step 3 : set maxlength :=0

lastIndex :=-1

Step 4 : for i := 0 to num length :

for j := 0 to i :

If num[i] % num[j] == 0 and dp[j]+1 > dp[i] :

dp[i]=dp[j]+1

prev[i]=j

If dp[i] > maxLength :

maxLength=dp[i]

lastIndex=i

42 of 171

Algorithm :

Step 5 : Create a linked list lis

Step 6 : while lastIndex != -1 :

Add num[lastIndex] to the first position of lis

lastIndex = prev[lastIndex]

Step 7 : return lis

Note : Length of lis will give you length of longest divisible subset

prev array is not required if we only need length ( maxLength variable have it )

We need prev array for reconstruction of subsequence

43 of 171

Code ( In Java ) :

44 of 171

Code ( In Java ) :

45 of 171

Code ( In Java ) :

46 of 171

Few more Test Cases :

47 of 171

Analysis :

Space Complexity :

Input : array requires O(n) space
Dp array requires O(n) space
Prev Array requires O(n) space
Total: O( n+n+n ) = O( 3n ) = O(n)

Time Complexity :

For each index i ,we check all previous elements using j which results in n(n-1)/2 comparisons
Hence, time complexity is O(n²)

48 of 171

Multistage Graph Algorithm :

Problem Statement :

Given a directed graph G=(V,E) with n vertices.

Vertices are partitioned into stages S0,S1,S2S3,.....,Sk-1

Vertices are arranged in k stages and edges only connect vertices of stage i and stage i+1 (i.e. edges go only from one stage to the next, never backward or skipping stages)
Find minimum cost path from source vertex to destination vertex
Source node (S1) is first node and destination node is last vertex (Sk)

Example: Here source is 0 and destination is 3

0

1

2

3

10

5

2

3

Minimum cost path will be 0↦2↦3

With cost = 5 + 3 =8

S0

S1

S2

49 of 171

Example :

0

1

2

3

4

5

6

7

8

9

10

11

12

13

2

5

1

10

6

12

4

8

20

7

15

22

3

9

13

2

4

5

3

10

1

S0

S1

S2

S3

S4

S5

Here both forward movement (from source to destination) and backward movement (from destination to source) gives correct output

By starting at the destination (which trivially has zero cost to itself), we ensure that when processing a node, all the nodes it can reach in the next stage have already been processed and their minimum costs calculated

In a forward movement, you don’t know the cost to reach the destination from your next node yet; DP needs subproblems to be solved before the current problem

50 of 171

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	∞	2	5	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	∞	∞	∞	∞	10	∞	∞	∞	∞	∞	∞	∞	∞	∞
2	∞	∞	∞	∞	6	∞	∞	∞	∞	∞	∞	∞	∞	∞
3	∞	∞	∞	∞	4	12	∞	∞	∞	∞	∞	∞	∞	∞
4	∞	∞	∞	∞	∞	∞	8	∞	20	7	∞	∞	∞	∞
5	∞	∞	∞	∞	∞	∞	∞	22	∞	15	∞	∞	∞	∞
6	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3	∞	∞
7	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	9	13	∞	∞
8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	2	∞	∞
9	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4	5	∞
10	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3
11	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
12	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	10
13	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

Adjacency Matrix :

51 of 171

dp													(∞) 10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	(-1) 13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 10 != ∞ and 0 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 10 + 0 =10

Is cost < dp[i] ?

( 10 < ∞ ) ?

True

dp[i] = cost = 10

next[i] = j = 13

52 of 171

dp												∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

53 of 171

dp												(∞) 1	10	0
	0	1	2	3	4	5	6	7	8	9	10	12	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	(-1) 13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 1 != ∞ and 0 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 1 + 0 =1

Is cost < dp[i] ?

( 1 < ∞ ) ?

True

dp[i] = cost = 1

next[i] = j = 13

54 of 171

dp											∞	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and ∞ != 1 )

False

55 of 171

dp											∞	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

56 of 171

dp											(∞) 3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	(-1) 13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 3 != ∞ and 0 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 3 + 0 =1

Is cost < dp[i] ?

( 3 < ∞ ) ?

True

dp[i] = cost = 3

next[i] = j = 13

57 of 171

dp										∞	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

58 of 171

dp										(∞) 5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	(-1) 11	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 4 != ∞ and 1 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 4 + 1 =5

Is cost < dp[i] ?

( 5 < ∞ ) ?

True

dp[i] = cost = 5

next[i] = j = 11

59 of 171

dp										5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	11	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 5 != ∞ and 10 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 5 + 10 =15

Is cost < dp[i] ?

( 15 < 5 ) ?

False

60 of 171

dp										5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	11	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

61 of 171

dp									∞	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

62 of 171

dp									∞	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	-1	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

63 of 171

dp									(∞) 3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	(-1) 11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 2 != ∞ and 1 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 2 + 1 =3

Is cost < dp[i] ?

( 3 < ∞ ) ?

True

dp[i] = cost = 3

next[i] = j = 11

64 of 171

dp									3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

65 of 171

dp									3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

66 of 171

dp								∞	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

67 of 171

dp								∞	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	-1	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

68 of 171

dp								(∞) 12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	(-1) 10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 9 != ∞ and 3 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 9 + 3 =12

Is cost < dp[i] ?

( 12 < ∞ ) ?

True

dp[i] = cost = 12

next[i] = j = 10

69 of 171

dp								12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 13 != ∞ and 1 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 13 + 1 =14

Is cost < dp[i] ?

( 14 < 12 ) ?

False

70 of 171

dp								12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

71 of 171

dp								12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

72 of 171

dp							∞	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

73 of 171

dp							∞	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

74 of 171

dp							∞	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

75 of 171

dp							∞	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	-1	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

76 of 171

dp							(∞) 4	12	3	15	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	(-1) 11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 3 != ∞ and 1 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 3 + 1 =4

Is cost < dp[i] ?

( 4 < ∞ ) ?

True

dp[i] = cost = 4

next[i] = j = 11

77 of 171

dp							4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

78 of 171

dp							4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

79 of 171

dp						∞	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	-1	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 4 != ∞ )

False

80 of 171

dp						(∞) 34	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	(-1) 7	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 22 != ∞ and 12 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 22 + 12 =34

Is cost < dp[i] ?

( 34 < ∞ ) ?

True

dp[i] = cost = 34

next[i] = j = 7

81 of 171

dp						(34) 18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	(7) 8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 15 != ∞ and 3 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 15 + 3 =18

Is cost < dp[i] ?

( 18 < 34 ) ?

True

dp[i] = cost = 18

next[i] = j = 8

82 of 171

dp						18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 15 != ∞ and 5 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 15 + 5 =20

Is cost < dp[i] ?

( 20 < 18 ) ?

False

83 of 171

dp						18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

84 of 171

dp						18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

85 of 171

dp						18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

86 of 171

dp						18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

87 of 171

dp					∞	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 18 != ∞ )

False

88 of 171

dp					(∞) 12	18	4	12	3	15	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	-1) 6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 8 != ∞ and 4 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 8 + 4 =12

Is cost < dp[i] ?

( 12 < ∞ ) ?

True

dp[i] = cost = 12

next[i] = j = 6

89 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

90 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 20 != ∞ and 3 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 20 + 3 =23

Is cost < dp[i] ?

( 23 < 12 ) ?

False

91 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 7 != ∞ and 5 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 7 + 5 =12

Is cost < dp[i] ?

( 12 < 12 ) ?

False

92 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

93 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

94 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

95 of 171

dp					12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	-1	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

96 of 171

dp				(∞) 16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	(-1) 4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 4 != ∞ and 12 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 4 + 12 =16

Is cost < dp[i] ?

( 16 < ∞ ) ?

True

dp[i] = cost = 16

next[i] = j = 4

97 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 12 != ∞ and 18 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 12 + 18 =30

Is cost < dp[i] ?

( 30 < 16 ) ?

False

98 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 4 != ∞ )

False

99 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

100 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

101 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

102 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

103 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

104 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

105 of 171

dp				16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

106 of 171

dp			∞	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	-1	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 16 != ∞ )

False

107 of 171

dp			(∞) 18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	(-1) 4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 6 != ∞ and 12 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 6 + 12 =18

Is cost < dp[i] ?

( 18 < ∞ ) ?

True

dp[i] = cost = 18

next[i] = j = 4

108 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 18 != ∞ )

False

109 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 4 != ∞ )

False

110 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

111 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

112 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

113 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

114 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

115 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

116 of 171

dp			18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

117 of 171

dp		∞	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 18 != ∞ )

False

118 of 171

dp		∞	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	-1	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 16 != ∞ )

False

119 of 171

dp		(∞) 22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	(-1) 4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 10 != ∞ and 22 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 10 + 12 =22

Is cost < dp[i] ?

( 22 < ∞ ) ?

True

dp[i] = cost = 32

next[i] = j = 4

120 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 18 != ∞ )

False

121 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 4 != ∞ )

False

122 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

123 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

124 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

125 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

126 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

127 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

128 of 171

dp		22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	-1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

129 of 171

dp	(∞) 24	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	(-1) 1	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 2 != ∞ and 22 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 2 + 22 =24

Is cost < dp[i] ?

( 24 < ∞ ) ?

True

dp[i] = cost = 24

next[i] = j = 1

130 of 171

dp	(24) 23	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	(1) 2	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 5 != ∞ and 18 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 5 + 18 =23

Is cost < dp[i] ?

( 23 < 24 ) ?

True

dp[i] = cost = 23

next[i] = j = 2

131 of 171

dp	(23) 17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	(2) 3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( 1 != ∞ and 16 != ∞ )

True

cost = graph[i][j] + dp[j]

cost = 1 + 16 =17

Is cost < dp[i] ?

( 17 < 23 ) ?

True

dp[i] = cost = 17

next[i] = j = 3

132 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

133 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 18 != ∞ )

False

134 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 4 != ∞ )

False

135 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 12 != ∞ )

False

136 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

137 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 5 != ∞ )

False

138 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 3 != ∞ )

False

139 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 1 != ∞ )

False

140 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 10 != ∞ )

False

141 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

i

j

Is graph[i][j] != ∞ and dp[j] != ∞ ?

( ∞ != ∞ and 0 != ∞ )

False

142 of 171

dp	17	22	18	16	12	18	4	12	3	5	3	1	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

cur = 0

Linked list path

Is cur != -1 ?

( 0 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =3

0

Linked list

path

143 of 171

dp	27	32	28	26	22	30	∞	∞	∞	15	∞	∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Is cur != -1 ?

( 3 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =4

0

Linked list

path

3

144 of 171

dp	27	32	28	26	22	30	∞	∞	∞	15	∞	∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Is cur != -1 ?

( 4 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =6

0

Linked list

path

3

4

145 of 171

dp	27	32	28	26	22	30	∞	∞	∞	15	∞	∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Is cur != -1 ?

( 6 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =11

0

Linked list

path

3

4

6

146 of 171

dp	27	32	28	26	22	30	∞	∞	∞	15	∞	∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Is cur != -1 ?

( 11 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =13

0

Linked list

path

3

4

6

11

147 of 171

dp	27	32	28	26	22	30	∞	∞	∞	15	∞	∞	10	0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

next	3	4	4	4	6	8	11	10	11	12	13	13	13	-1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Is cur != -1 ?

( 13 != -1 ) ?

True

Add cur to path

cur = next[cur]

cur =-1

0

Linked list

path

3

4

6

11

13

148 of 171

Algorithm :

Step 1 : Input numbers in graph array and number of nodes ( numNodes )

Step 2 : Initialize dp[numNode-1] array with 0 (size numNodes) with and next array (size numNodes) with -1

Step 3 : Set cost = 0

Step 4 : for i := numNodes-2 to 0 :

dp[i] = ∞:

for j := i+1 to numNodes :

If graph[i][j] != ∞ dp[j] != ∞:

cost = graph[i][j] + dp[j]

If cost < dp[i] :

dp[i] = cost

next[i] = j

149 of 171

Step 5 : create list path

Step 6 : cur = 0

while cur != -1 do :

path.add(cur)

cur = next[cur]

Step 7 : return dp[0] and path

Note : Here in Step 4 inner loop can be iterated k times where k is the stage for next node, it optimize the solution.

It is not possible to know every time, the number of stages present in graph

As graph in the example has 14 nodes so it is tedious to type these many inputs so randomly graph adjacency matrix was generated, so it is not possible to know number of stages hence general inner loop is written which can work for these cases

150 of 171

Code ( in java ) :

151 of 171

Code ( in java ) :

152 of 171

Code ( in java ) :

153 of 171

Test Cases :

154 of 171

Analysis :

Space Complexity :

Input array requires O(n²) space
Dp array requires O(n) space
Near Array requires O(n) space
Total: O( n²+n+n ) = O( n²+ 2n ) = O(n²)
Space bottleneck is adjacency matrix for large n, consider adjacency list for large, sparse graphs.

Time Complexity :

For each index i ,we check all next elements using j which results in n(n-1)/2 comparisons
Hence, time complexity is O(n²)
For a layered/strict multistage graph, if you limit edges only to next-stage nodes, total edges E, E is much smaller and performance is close to linear O( n )

155 of 171

Minimum Path Sum In a Grid :

Problem Statement :

Given an n × m grid with non-negative numbers, find the path from top-left corner to bottom-right corner which minimizes the sum of all numbers along the path.

Movement allowed strictly in two directions i.e. in right or down of the cell
m and n may or may not be equal
Must accumulate the sum of all cell values visited, including the starting and ending cells

Extra task :

To compare outputs of two different algorithms - Dynamic Programming and Greedy algorithm

Example: we will get minimum sum from path 1→0→5 sum=6

1	2
0	5

156 of 171

Example (Dynamic Programming approach) :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

grid

	0	1	2
0	10	18	20
1	20
2	21

dp array

For j=1 to m-1

dp[0][j] = dp[0][j - 1] + grid[0][j]

dp[0][1] = dp[0][0] + grid[0][1] = 10+8 =18

dp[0][2] = dp[0][1] + grid[0][2] = 18+2 =20

dp[0][0]=grid[0][0]=10

For i=1 to n-1

dp[i][0] = dp[i-1][0] + grid[i][0]

dp[1][0] = dp[0][0] + grid[1][0] = 10+10 =20

dp[2][0] = dp[1][0] + grid[2][0] = 20+1 =21

157 of 171

Example (Dynamic Programming approach) :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

grid

	0	1	2
0	10	18	20
1	20	23	120
2	21	22	24

dp array

For i=1 to n-1

For j=1 to m-1

dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]

dp[1][1]=grid[1][1]+min(dp[0][1],dp[1][0]) = 5+min(18,20) = 5+18 = 23

dp[1][2]=grid[1][2]+min(dp[0][2],dp[1][1]) = 100+min(20,23) = 100+20 = 120

dp[2][1]=grid[2][1]+min(dp[1][1],dp[2][0]) = 1+min(23,21) = 1+21 = 22

dp[2][2]=grid[2][2]+min(dp[1][2],dp[2][1]) = 2+min(120,22) = 2+22 = 24

158 of 171

Example (Dynamic Programming approach) :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

grid

	0	1	2
0	10	18	20
1	20	23	120
2	21	22	24

dp array

{2,2}	{2,1}	{2,0}	{1,0}	{0,0}

path

Set i = n-1 (2) and j = m-1 (2)

For i>=0 and j>=0

Add {i,j} ({2,2}) to path

Is i==0 (2 == 0) False

Is j==0 (2 == 0) False

Is dp[i - 1][j] < dp[i][j - 1]

( 120 < 22 )? False

j = j-1 = 1

Add {i,j} ({2,1}) to path

Is i==0 (2 == 0) False

Is j==0 (1 == 0) False

Is dp[i - 1][j] < dp[i][j - 1]

( 23 < 21 )? False

j = j-1 = 0

Add {i,j} ({2,0}) to path

Is i==0 (2 == 0) False

Is j==0 (0 == 0) True

i = i-1 = 1

Add {i,j} ({1,0}) to path

Is i==0 (1 == 0) False

Is j==0 (0 == 0) True

i = i-1 = 0

Add {i,j} ({0,0}) to path

Is i==0 (0 == 0) True

j = j-1 =-1

Stop iterations

159 of 171

Example (Dynamic Programming approach) :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

grid

	0	1	2
0	10	18	20
1	20	23	120
2	21	22	24

dp array

{2,2}	{2,1}	{2,0}	{1,0}	{0,0}

path

Reverse the path

{0,0}	{1,0}	{2,0}	{2,1}	{2,2}

path

160 of 171

Example (Greedy approach) :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

grid

{0,0}	{0,1}	{0,2}	{1,2}	{2,2}

path

Set i = 0 and j = 0

For i<=n-1 and j<= m-1

Add {i,j} ({0,0}) to path

Is i==n-1 (0 == n-1(2)) False

Is j==m-1 (0 == m-1 (2)) False

Is grid[i+1][j] < grid[i][j+1] ?

( 10 < 8 )? False

j = j+1 = 1

Add {i,j} ({0,1}) to path

Is i==0 (0 == 2) False

Is j==0 (1 == 2) False

Is grid[i+1][j] < grid[i][j+1] ?

( 5 < 2 )? False

j = j+1 = 2

Add {i,j} ({0,2}) to path

Is i==0 (0 == 2) False

Is j==0 (2 == 2) True

i=i+1=1

Add {i,j} ({1,2}) to path

Is i==0 (1 == 2) False

Is j==0 (2 == 2) True

i=i+1=2

Add {i,j} ({2,2}) to path

Is i==0 (2 == 2) True

j=j+1=3

Stop iterations

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

Grid with path

161 of 171

Comparison :

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

Grid (DP)

{0,0}	{1,0}	{2,0}	{2,1}	{2,2}

Path dp

	0	1	2
0	10	8	2
1	10	5	100
2	1	1	2

Grid Greedy

{0,0}	{0,1}	{0,2}	{1,2}	{2,2}

Path Greedy

Sum = 24

Sum = 122

Aspect	Dynamic Programming	Greedy
Decision Basis	Considers subproblem solutions and global min	Chooses local minimum cost step
Optimality Guarantee	Yes	No (only for specific problem types)
Subproblem Overlap	Yes, results stored and reused	No
Backtracking	Implicit via table, explores all paths	None
Efficiency	Efficient and correct for this problem	Simple but can be incorrect

162 of 171

Algorithm (Dynamic Programming):

Step 1 : Input numbers in grid array

Step 2 : Initialize n with number of rows in grid and m with number of columns in grid

Step 3 : Set dp[0][0] = grid[0][0]

Step 4 : for i := 1 to m-1:

dp[0][j] = dp[0][j - 1] + grid[0][j]

Step 5 : for j := n-1:

dp[i][0] = dp[i - 1][0] + grid[i][0]

Step 6 : Set i := n-1 and j := m-1, Add {i,j} to path

while i >= 0 and j >=0 :

if i == 0

j=j-1

else if j==0

i=i-1

else if dp[i - 1][j] < dp[i][j - 1] :

i=i-1

else

j=j-1

Add {i,j} to path

Reverse the path

Step 7 : return path

163 of 171

Algorithm (Greedy) :

Step 1 : Input numbers in grid array

Step 2 : Initialize n with number of rows in grid and m with number of columns in grid

Step 3 : Set i=0 and j=0

Add {i,j} to path

while i != n-1 or j != m-1 :

if i==n-1 :

j=j+1

else if j==m-1 :

i=i+1

else if grid[i+1][j] < grid[i][j+1]

i=i+1

else

j=j+1

Add {i,j} to path

Step 4 : return path

Note: To calculate the sum in both algorithms follow the path and add all values visited along it

164 of 171

Code ( In Java ) :

165 of 171

Code ( In Java ) :

166 of 171

Code ( In Java ) :

167 of 171

Test cases :

168 of 171

Analysis :

Space Complexity :

Input array requires O(n×m) space
Dp array requires O(n×m) space
path Array requires O(n+m) space
Total: O( n×m + n×m + n+m ) = O( 2×n×m + n+m ) = O(n×m)

Time Complexity :

For each (i,j) we check top and left so constant work
Hence, the total time taken is proportional to the number of cells
Time complexity : O(n×m)

169 of 171

Real World Applications :

Longest Increasing Subsequence (LIS)

Stock market analysis: Find the longest period over which stock prices strictly increased, which is essential for financial modeling and trading strategy evaluation.
Project scheduling: Determine the longest sequence of tasks that must be done in increasing order, such as project milestones or dependency chains.
Bioinformatics: Analyze DNA or protein sequences to find the longest stretch of increasing data, useful in evolutionary biology.
Version control systems: Track the longest sequence of upgrades or commits without regression to earlier versions.

Longest Divisible Subset

Cryptography: Identify hierarchical groupings where divisibility matters (such as key scheduling or cryptographic protocols).
Database normalization: Find sets of data elements (like IDs, timestamps) that are neatly divisible for storage optimization.
Data clustering: Group numbers into maximally cohesive sets for compression or grouping, such as packet sizes in network protocols.
Mathematical modeling: Useful in problems where grouping numbers by divisibility simplifies constraints or enhances performance.

170 of 171

Real World Applications :

Multistage Graph Algorithm

Supply chain and logistics: Optimize transportation or assembly line routes that naturally proceed through defined "stages" (like warehouses, ports, or checkpoints).
Telecommunications: Route data efficiently in layered or hierarchical network topologies.
Manufacturing processes: Model assembly and fabrication processes, ensuring minimal transition cost between consecutive stages.
Project planning: Structure large projects as workflows or graphs, ensuring minimum cost and efficient progression through phases.

Minimum Path Sum in a Grid

Robotics and path planning: Enable robots to compute the least-energy or least-danger route in environments modeled as grids (warehouses, factories, fields).
Image processing: Seam carving (content-aware image resizing) uses similar minimum energy paths for optimal pixel removal.
Network routing: Find the least-cost path for data packets traversing 2D grid-based sensor networks.
Urban planning: Design the layout of roads or pipelines where movement is restricted to horizontal and vertical directions, minimizing construction cost.

171 of 171

Further reference: github repository - https://github.com/antara2409/Design_and_Analysis_of_Algorithms_Codes/tree/main

Contact : Email address - 24kawathekara@rbunagpur.in

Thank you!

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	∞	2	5	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	∞	∞	∞	∞	10	∞	∞	∞	∞	∞	∞	∞	∞	∞
2	∞	∞	∞	∞	6	∞	∞	∞	∞	∞	∞	∞	∞	∞
3	∞	∞	∞	∞	4	12	∞	∞	∞	∞	∞	∞	∞	∞
4	∞	∞	∞	∞	∞	∞	8	∞	20	7	∞	∞	∞	∞
5	∞	∞	∞	∞	∞	∞	∞	22	∞	15	∞	∞	∞	∞
6	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3	∞	∞
7	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	9	13	∞	∞
8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	2	∞	∞
9	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4	5	∞
10	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3
11	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
12	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	10
13	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	∞	2	5	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	∞	∞	∞	∞	10	∞	∞	∞	∞	∞	∞	∞	∞	∞
2	∞	∞	∞	∞	6	∞	∞	∞	∞	∞	∞	∞	∞	∞
3	∞	∞	∞	∞	4	12	∞	∞	∞	∞	∞	∞	∞	∞
4	∞	∞	∞	∞	∞	∞	8	∞	20	7	∞	∞	∞	∞
5	∞	∞	∞	∞	∞	∞	∞	22	∞	15	∞	∞	∞	∞
6	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3	∞	∞
7	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	9	13	∞	∞
8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	2	∞	∞
9	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4	5	∞
10	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3
11	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
12	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	10
13	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	∞	2	5	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	∞	∞	∞	∞	10	∞	∞	∞	∞	∞	∞	∞	∞	∞
2	∞	∞	∞	∞	6	∞	∞	∞	∞	∞	∞	∞	∞	∞
3	∞	∞	∞	∞	4	12	∞	∞	∞	∞	∞	∞	∞	∞
4	∞	∞	∞	∞	∞	∞	8	∞	20	7	∞	∞	∞	∞
5	∞	∞	∞	∞	∞	∞	∞	22	∞	15	∞	∞	∞	∞
6	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3	∞	∞
7	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	9	13	∞	∞
8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	2	∞	∞
9	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4	5	∞
10	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3
11	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
12	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	10
13	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞