Thinking from bottom to top.
For the finish position which is pathsToPosition[m][n], there are two ways to go there
from left position [m - 1][n] or top position [m][n - 1]. Same for any other positions.
So we can start from the top left position which there is only 1 way to reach
Then write nested for loop to check for all the other positions
Until reaching [m][n] which is the final result
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q060UniquePaths.playground/Contents.swift
No comments:
Post a Comment