每日leetcode第0040天 0279. Perfect Squares

这是一道动态规划的题目,利用了一些数学的原理。

转移方程是核心,就是要尝试减去每一种平方,看看减去之后的过往情况那个数最小。

所以这道题的状态转移方程式是带有循环的。

最后求出最小值后不能忘记要加一。

 

初始化initialization:
ps[0] = 0;

状态转移方程式optimum-value function:
int min_ps = INT_MAX;
for (int j = 1; j * j <= i; ++j) {
min_ps = min(min_ps, ps[i – j * j]);
}
ps[i] = min_ps + 1;

循环公式recurrent formula:
for (int i = 1; i <= n; ++i) {
}



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。