课程: Advanced Go Programming: Data Structures, Code Architecture, and Testing

Solution: Counting paths - Go教程

课程: Advanced Go Programming: Data Structures, Code Architecture, and Testing

开始一个月试用

Solution: Counting paths

“

(upbeat music) - [Instructor] Let's have a look at my solution to the counting paths with a given cost challenge. I haven't modified any of the provided code, only changing the countPaths function to use dynamic programming. You can see the solution on line 60 to 100. We will be working with a recursive function so begin by checking the base cases first. On lines 62 to 64, check whether the cost is negative. In this case, we've exceeded the provided cost and we haven't found a valid path. We return zero in this case. Next, on lines 67 to 69, try to fetch a pre-computed path count from the maze if this subproblem has been solved already. If a value is found as indicated by the returned OK value, simply return the fetched value and spare all later recomputation. Next, on line 71 to 80, first retrieve the cost of the current element, then handle the case that the destination has been reached. If we've reached the destination, then we found a valid path if the cost of the current element is the same as the path cost and return one. Otherwise, it's an invalid path and our function returns zero. After these end cases, we'll need to do further computation as we haven't reached the end of our budget or the destination. Further down on lines 83 to 87, check whether we are on the last row. In this case, we are only permitted to make moves to the right, invoke the countPaths function recursively with the permitted move, incrementing the column index and decreasing the cost, In the same way on lines 89 to 93, check whether we are on the last column. In this case, we're only permitted to move downwards and invoke the countPaths function recursively with an incremented row index. We could have chosen not to handle the last row and last column cases on their own by incrementing indices outside the bounds of the maze. However, I made the choice not to generate invalid moves at the cost of slightly longer code. Finally, if none of these cases are true, we're in the middle of the maze. In this case, we invoke the countPaths function twice with both valid moves to the right and downwards. That's all the code we need to count the paths of a matrix of a given cost. Let's run the code using the Test My Code button. The solution is just as expected. We've successfully implemented the fourth challenge by making use of the dynamic programming techniques of recursion and memoization. Well done.

内容