Introduction to Dynamic Programming (DP) - Go教程

- [Instructor] Now, let's focus on the topic of dynamic programming, often shortened to DP. Many engineers find this topic intimidating, but it's a useful tool once you're comfortable with it. Let's start with the core concepts of dynamic programming. Dynamic programming is a technique which allows us to solve complex problems by solving related smaller subproblems. The solutions to the subproblems are then stored in memory or some other structure to be later combined into the solution to the original problem. When solving problems with DP, you'll want to follow a defined four step process. Begin by identifying the problem and representing it in algorithmic form. Oftentimes, the problem will be formulated in words and not represented with data structures. Next, break down the problem into simpler subproblems, and identify the relationship between the subproblems. This step is crucial to understanding whether dynamic programming is a suitable solution for the problem. Third, implement the algorithm. At this point, we have everything we need to implement the algorithm required to solve the problem. It will consist of all the cases we need to solve, as well as the end condition of the algorithm. Finally, define and implement how to build the solution by combining the solutions to the subproblems. These solutions can be saved through recursive function calls or in another data structure. Dynamic programming can be used for solving a variety of problems. You can see some of its common uses here. Firstly, DP can be useful for solving optimization problems. It can find the best solution from a finite set of possibilities. Common problems of this type are maximum sub array or substring challenges. One of the best known challenge of this type is the traveling salesman problem. Secondly, DP can be useful for solving graph traversal and search problems. This approach can make it easy to construct a list of available paths, and then find the best one that fits a certain criteria. Common problems of this type are calculating shortest paths or maximum sums of weighted graphs. Thirdly, DP can be useful for solving perfect information games. Such games are turn-based, and all the players have access to the same information regarding previous moves. This approach can find the best moves from a constructed list of alternatives. Popular problems of this type are constructing a chess engine or making moves in a game of goal. You are now up to speed on how dynamic programming makes it easy to solve a wide variety of problems. It's worthwhile learning this style of programming. You'll practice it in an upcoming challenge.