Optimal substructure & Overlapping subproblems
最近在做题过程中，对于一些概念变得模糊了，导致其实有时候拿不准是否该使用动态规划思路去解题，以及其中的一些解题思想。
结合自己之前的笔记，又在网上看到了一个文章，觉得不错转载过来分享和记录。动态规划之武林秘籍
-
动态规划算法与分治法类似，其基本思想就是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。
-
最优子结构: 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质
-
重叠子问题: 在用递归算法自顶向下解决一个问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
-
何时考虑动态规划
一般情况下，需要求最优解的问题（最短路径问题，最长公共子序列，最大字段和等等，出现 最 字你就留意），在一定条件下对排列进行计数的计数问题（丑数问题）或某些概率问题都可以考虑用动态规划来解决。
所有的动态规划问题都满足重叠子问题性质，大多数经典的动态规划问题还满足最优子结构性质，当我们从一个给定的问题中发现了这些特性，就可以确定其可以用动态规划解决。
Recently, in the process of doing problems, some concepts have become blurred, resulting in the fact that sometimes it is not possible to use dynamic planning ideas to solve the problem, as well as some of the ideas to solve the problem.
I think it's a good idea to share and record this article with my previous notes. Dynamic planning of the martial arts secret
-
The dynamic programming algorithm is similar to the partitioning method. The basic idea is to decompose the problem to be solved into several subproblems, solve the subproblems first, and then get the solution of the original problem from the solution of these subproblems. Unlike the partitioning method, problems suitable for dynamic programming are often not mutually independent of the subproblems obtained by the decomposition.
-
Optimal substructure: When the optimal solution of a problem contains the optimal solutions of its subproblems, the problem is said to have the property of optimal substructure.
-
Overlapping subproblems: When solving a problem top-down with a recursive algorithm, each resulting subproblem is not always a new problem; some subproblems are computed multiple times.
-
When to consider dynamic programming
In general, problems that require optimal solutions (shortest path problems, longest common subsequence, maximal field sums, etc., look for most words when they appear), counting problems that count permutations under certain conditions (ugly number problems), or certain probability problems can be considered for dynamic programming.
All dynamic programming problems satisfy the overlapping subproblem property, and most classical dynamic programming problems also satisfy the optimal substructure property. When we find these properties from a given problem, we can determine that it can be solved by dynamic programming.