4 Key Points of DP and Coordinate DP

A robot is located at the top-left corner of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

m and n will be at most 100.
The answer is guaranteed to be in the range of 32-bit integers

Example 1:

Input: n = 1, m = 3
Output: 1
Explanation: Only one path to target position.

Example 2:

Input:  n = 3, m = 3
Output: 6
Explanation:
D : Down
R : Right
1) DDRR
2) DRDR
3) DRRD
4) RRDD
5) RDRD
6) RDDR

Solution:

def c(self, m, n):
mp = {}
for i in range(m):
for j in range(n):
if(i == 0 or j == 0):
mp[(i, j)] = 1
else:
mp[(i, j)] = mp[(i - 1, j)] + mp[(i, j - 1)]
return mp[(m - 1, n - 1)]
def uniquePaths(self, m, n):
return self.c(m, n)

2.Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

m and n will be at most 100.

Example

Example 1:
Input: [[0]]
Output: 1
Example 2:
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Explanation:
Only 2 different path.

Solution:

def uniquePathsWithObstacles(self, obstacleGrid):
mp = obstacleGrid
for i in range(len(mp)):
for j in range(len(mp[i])):
if i == 0 and j == 0:
mp[i][j] = 1 - mp[i][j]
elif i == 0:
if mp[i][j] == 1:
mp[i][j] = 0
else:
mp[i][j] = mp[i][j - 1]
elif j == 0:
if mp[i][j] == 1:
mp[i][j] = 0
else:
mp[i][j] = mp[i - 1][j]
else:
if mp[i][j] == 1:
mp[i][j] = 0
else:
mp[i][j] = mp[i - 1][j] + mp[i][j - 1]
if mp[-1][-1] > 2147483647:
return -1
else:
return mp[-1][-1]

3. Climbing StairsFollow

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:
Input: n = 3
Output: 3

Explanation:
1) 1, 1, 1
2) 1, 2
3) 2, 1
total 3.


Example 2:
Input: n = 1
Output: 1

Explanation:
only 1 way.

Solution:

def climbStairs(self, n):
if n == 0:
return 0
if n <= 2:
return n
result=[1,2]
for i in range(n-2):
result.append(result[-2]+result[-1])
return result[-1]

4. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

You can only go right or down in the path..

Example 1:
Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7

Explanation:
Path is: 1 -> 3 -> 1 -> 1 -> 1


Example 2:
Input: [[1,3,2]]
Output: 6

Explanation:
Path is: 1 -> 3 -> 2

Solution:

def minPathSum(self, grid):
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == 0 and j > 0:
grid[i][j] += grid[i][j-1]
elif j == 0 and i > 0:
grid[i][j] += grid[i-1][j]
elif i > 0 and j > 0:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[len(grid) - 1][len(grid[0]) - 1]

5. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: nums =  [1,2,3], 
Output: [1,2] or [1,3]

Example 2:

Input: nums = [1,2,4,8], 
Output: [1,2,4,8]

Solution:

def largestDivisibleSubset(self, nums):
n = len(nums)
dp = [1] * n
father = [-1] * n
nums.sort()
m, index = 0, -1
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0:
if 1 + dp[j] > dp[i]:
dp[i] = dp[j] + 1
father[i] = j
if dp[i] >= m:
m = dp[i]
index = i
result = []
for i in range(m):
result.append(nums[index])
index = father[index]
return result

6. Knight Shortest Path

Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if destination cannot be reached.

source and destination must be empty.
Knight can not enter the barrier.
Path length refers to the number of steps the knight takes.

Clarification

If the knight is at (x, y), he can get to the following positions in one step:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

Example 1:

Input:
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2]
Output: 2
Explanation:
[2,0]->[0,1]->[2,2]

Example 2:

Input:
[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2]
Output:-1

Solution:

def shortestPath(self, grid, source, destination):
directions = [
(-2, -1), (-2, 1), (-1, 2), (1, 2),
(2, 1), (2, -1), (1, -2), (-1, -2),
]

queue = collections.deque([(source.x, source.y)])
distance = {(source.x, source.y): 0}

while queue:
x, y = queue.popleft()
if(x, y) == (destination.x, destination.y):
return distance[(x,y)]
for dx, dy in directions:
next_x = x + dx
next_y = y + dy
if (next_x, next_y) in distance:
continue
if not self.is_valid(next_x, next_y, grid):
continue
queue.append((next_x, next_y))
distance[(next_x, next_y)] = distance[(x, y)] + 1
return -1



def is_valid(self, x, y, grid):
row, col = len(grid), len(grid[0])
if x < 0 or x >= row or y < 0 or y >= col:
return False
return not grid[x][y]

7. Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Clarification

What’s the definition of longest increasing subsequence?

  • The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
  • https://en.wikipedia.org/wiki/Longest_increasing_subsequence
Example 1:
Input: [5,4,1,2,3]
Output: 3

Explanation:
LIS is [1,2,3]


Example 2:
Input: [4,2,4,5,3,7]
Output: 4

Explanation:
LIS is [2,4,5,7]

Solution:

def longestIncreasingSubsequence(self, nums):
if nums is None or not nums:
return 0
dp = [1] * len(nums)
for curr, val in enumerate(nums):
for prev in range(curr):
if nums[prev] < val:
dp[curr] = max(dp[curr], dp[prev] + 1)
return max(dp)

8. Russian Doll Envelopes

Give a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
Find the maximum number of nested layers of envelopes.

Example 1:

Input:[[5,4],[6,4],[6,7],[2,3]]
Output:3
Explanation:
the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input:[[4,5],[4,6],[6,7],[2,3],[1,1]]
Output:4
Explanation:
the maximum number of envelopes you can Russian doll is 4 ([1,1] => [2,3] => [4,5] / [4,6] => [6,7]).

Solution:

def maxEnvelopes(self, envelopes):
height = [a[1] for a in sorted(envelopes, key = lambda x: (x[0], -x[1]))]
dp, length = [0] * len(height), 0
import bisect
for h in height:
i = bisect.bisect_left(dp, h, 0, length)
dp[i] = h
if i == length:
length += 1
return length

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store