问题:我知道递归是如何工作的，但我似乎无法理解这个问题的“最优子结构”，这需要使用动态规划。
问题:找出总和为给定数的最少完全平方数。
假设我们想要找到从 U 到 V 的最短路径。如果中间有一个节点 X，那么从 U 到 V 的最短路径将是从 U 到 X 的最短路径加上从 X 到 V 的最短路径。
我很难理解最小二乘问题如何遵循最优子结构属性。
最佳答案
据我了解，完全平方和的递推关系与最短路径的递推关系在以下方面表现相似。让
f(n) := minimum number of perfect squares which sum up to exactly n
那么一个合适的递推可以表示为
f(n) = min{ f(n-i) + f(i) : 0 < i < n }
这意味着必须考虑将原始参数划分为两个被加数的所有部分。直觉上，最短路径问题的“ split 点”是一个节点，而在完全平方问题中，它是决定如何划分为被加数(然后进一步检查)。
关于algorithm - 最少完美正方形的最佳子结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35425342/