动态规划法之最优性原理教学

The Teaching of Optimization Principle for Dynamic Programming

最优性原理是使用动态规划法的必要条件，该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法，先假设所导出的子问题的解不是最优的，进而说明可构造比原问题最优解更好的解，从而矛盾。

Optimization principle is a necessary condition for dynamic programming, It is a hard task that understand and prove the principle in algorithm teaching. It is the key that distinguishing the sub-problem exported from the original problem＇s best solution. It usually proves the principle by reduction to absurdly. Assuming the sub-problem＇s solution is＇nt the best one, so we can construct a better solution for the original problem.