Assignment $3($Dynamic Programming$)$

Assignment Content

Using the code posted for Dynamic Programming. Complete both programming codes for $(1)$

Fibonacci numbers, and for

$(2)($optional$)$ combination numbers using the method of Dynamic Programming.

the code"

def minPathSum$($grid$)$:

$$# Get the number of rows $($m$)$ and columns $($n$)$

$$m$,$ n $=$ len$($grid$),$ len$($grid$[0])$

$$

$$# Initialize a $2$D DP array with the same size as the grid

$$dp $=[[0]*$ n for $\_$ in range$($m$)]$

$$

$$# Base case: the top$-$left corner is the starting point

$$dp$[0][0]=$ grid$[0][0]$

$$

$$# Fill the first row $($can only move right$)$

$$for j in range$(1,$ n$)$:

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

$$

$$# Fill the first column $($can only move down$)$

$$for i in range$(1,$ m$)$:

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

$$

$$# Fill the rest of the DP table

$$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 bottom$-$right corner will have the minimum path sum

$$return dp$[$m $-1][$n $-1]$

# Example usage:

grid $=[[1,3,1],$

$[1,5,1],$

$[4,2,1]]$

print$($minPathSum$($grid$))$# Output: $7"$

You can add time spending to the code for each calculation and compare them $($with or

without DP$)$ for extra points.

You can watch the video posted $($Unedited video, or the video on Youtube$).$