方格取数问题的动态规划算法

动态规划算法对很多实际问题的解决是灵活和高效的.首先对方格取数问题进行分析,通过一条路径和两条路径选择的对比分析,得出了该问题的动态规划算法,并对该算法关键部分加以代码实现,最后对该算法的时间和空间复杂度进行分析和讨论,并对复杂度进行优化.试验的结果说明了该算法对于解决该类问题在时间效率上要明显优于贪心算法等一些算法.

THE DYNAMIC PROGRAMMING ALGORITHM FOR DIGIT-PICKING IN CHECK CHART PROBLEM

The dynamic programming algorithm is flexible and effective for many problems in actual application.In this paper it first analyses the problem of digit-picking in check chart,and then gives the dynamic algorithm for this problem by the comparison of one-path and two-path selections,the main part of the algorithm has been implemented in codes as well.At last it discusses the complexity of the algorithm in time and space together with an optimization on it.Simulation results show that the algorithm outperfor...