Dynamic Programming Algorithm Is Applied On The Time Efficiency Is Optimized

The design of the algorithm is the main content of software design. As a mature technique of algorithm design, dynamic programming is widely used in industry, agriculture, economy, military, engineering and some other fields, which indicates that it is efficient and practical and it has a bright future. The dissertation deals with many aspects of dynamic programming. By using many examples of programming, it gives a detailed explanation of dynamic programming's rationale, application and optimization method. The details listed as follows:First, through the introduction of its essence, it introduces the definition of some terms such as multistage decision-making, stage and state, decision-making and strategy, optimality principle, non-aftereffect, optimal target function, programming equation and so on. By using some common examples, it gives a full description of the diversity, the pattern and the artifice of dynamic programming in designing and application. By comparing with some common algorithms, it explains their differences and relationships and emphasizes its characteristics--- optimized, efficient, and consumptive.Second, through solving three problems, we can find dynamic programming is a necessity. With the help of the following steps, like problem describing, sample analyzing, algorithm designing, problem solving and result testing, it gives a full explanation of the implementation process and thinking methods of dynamic programming in application. It also shows that dynamic programming is very useful and helpful in application.Third, There is a time redundancy after dynamic programming is used to design algorithm simply, so I try to optimize the dynamic programming in three aspects of time complexity---total quantities of state, state quantities of every state transition and time of every state transition, which helps it improve a lot in time efficiency and makes it possible for the newly-- designed algorithm to solve the problem with large-sized data. Not only does it provide the theoretical basis and methods of optimization, but also it provides the comparison results of five experiments before it optimized and after it optimized.In conclusion, the dissertation not only analyzes the improvements of the application and optimization of dynamic programming in solving other problems, but also points out the research direction of the work in the future.