Lucky Toll Trips
tolls is a grid of road tolls given as a list of rows, and a cell holding -1 is closed. A car drives from the top left cell to the bottom right cell, moving one cell right or one cell down at a time and never entering a closed cell. A trip is lucky when the sum of the tolls of all the cells it enters, the first and the last included, is divisible by k.
Return the number of lucky trips. If the start or the end cell is closed, return 0.
Example 1
Of the three trips, only right, right, down totals a multiple of 3: 1 + 2 + 3 + 6 = 12.
Example 2
Three trips avoid the closed cell. Two of them total 18, which is divisible by 3; the third totals 19.
Constraints
1 <= len(tolls) <= 101 <= len(tolls[0]) <= 10, every row the same lengthtolls[r][c]is-1or between 0 and 1001 <= k <= 20
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- No Double LeapsMedium
- One Forgiven DayMedium
- Paint the FenceMedium
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium
- Unique Grid PathsMedium
- Ways to Make ChangeMedium