3D DP
Dijkstra and Floyd Warshall Floyd War
3 min readFeb 7, 2020
A classical 3D DP example will be using Floyd Warshall to solve the APSP problem. APSP is short for all pair shortest path.
A problem related to using the Floyd Warshall algorithm can be found here.
1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
"""
# time complexity O(n*m*k*m).
# First nmk can be found from the 3 layer loops. The last m is we have sum(dp[i][j-1] for i in range(i)), Since 0 <= k <= n, the finaly time complexity will be O((nm)^2)# space complexity O(km) or O(nm)
"""class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
if k ==0 :return 0
dp = [[1]+[0]*(k-1) for _ in range(m)]
# dp[i][j] i means the MAX val so far is (i+1), here +1 is only changing the 0 based index to 1 based index, j means the value of k is (j+1)
# dp[i][j] looks back will have two cases, I'd like to explain it from an example.
# for example, if we want to get current MAX as 3, we have two cases:
# 1) the previous step already have a MAX of 3, then what we can pickup at this step is 1,2,3 and it will not change the MAX as 3 proerty.
# 2) the previous step MAX value is less than 3, we pick up 3 here to generate a MAX value as 3 case.
# the new_dp[3][5] below means current MAX values is 3 and 5 is only an example means the search_cost is 5. In order to main focus on the logic, I am using 1 based index here to explain. For the code, I use the 0 based index.
# new_dp[3][5] = previous_dp[3][5] + one from {1,2,3}
# +sum(previous_dp[x][4] for x in [1, 2])
for _ in range(n-1):
new_dp = [[0]*k for i in range(m)]
for i in range(m):
for j in range(k):
new_dp [i][j] += dp[i][j]*(i+1)
if j-1>=0:new_dp[i][j] += sum(dp[i][j-1] for i in range(i))
dp = new_dp
# the final output will be MAX value of 1 to m for all search_cost is equal to k cases. Here we are using k-1 as we are using 0 index
return sum(dp[i][k-1] for i in range(m))%(10**9+7)
# time complexity: O(m*n*m*n)
# Space complexity: O(m*n*m)
from functools import lru_cache
class Solution:
def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
@lru_cache(None)
def dp(i, c, t):
if t <=0:return float('inf')
# if pained last summer, we can not repain it to another color
if houses[i]!= 0 and houses[i] != c:return float('inf')
this_cost = cost[i][c-1] if houses[i]==0 else 0
if i==0:
# if we only have the first pain lest, we should only have one group
if t!=1:return float('inf')
return this_cost
return min(dp(i-1, color, t-int(c!=color)) for color in range(1, n+1)) + this_cost
res = min(dp(m-1, color, target) for color in range(1, n+1))
return res if res!=float('inf') else -12D DP
2D DP is summarized here:
