php做商城网站,建设银行内部学习网站,WordPress热门排行榜插件,南京中如建设公司文章目录题目描述思路 代码题目描述
类似找零钱#xff0c;思路和代码框架基本上一样
思路 代码
考虑到这么一点#xff1a;某完全平方数#xff0c;肯定是由另一更小的完全平方数 一平方组成比如 16 8 4 (完全平方数82222)22(完全平方数82^2 2^2) 2^…
文章目录题目描述思路 代码题目描述
类似找零钱思路和代码框架基本上一样
思路 代码
考虑到这么一点某完全平方数肯定是由另一更小的完全平方数 一平方组成比如 16 8 4 (完全平方数82222)22(完全平方数82^2 2^2) 2^2(完全平方数82222)22那么好办了直接用dp冲
class Solution {/*** 动态规划dp[i]代表 i 的完全平方数的最少数量* 如何考虑比如 dp[12] dp[8] 1 (此处为 2 * 2)* 也就是一个数一定是由某一个较小数的完全平方数 加上 一个整数的平方组成的*/public int numSquares(int n) {int[] dp new int[n 1];// 时间复杂度O(n * sqrt(n))for(int i 1; i n; i){// 初始化使用最差情况全为 1^2 组成dp[i] i;for(int j 1; i - j * j 0; j){// 下式中 1 就是 j * jdp[i] Math.min(dp[i], dp[i - j * j] 1);}}return dp[n];}
}时间复杂度为O(n * sqrt(n))代码重点是for j的循环结束条件 状态转移方程无注释版
class Solution {public int numSquares(int n) {int[] ans new int[n 1];for(int i 1; i n; i) {ans[i] i;for(int j 1; j * j i; j) {ans[i] Math.min(ans[i], ans[i - j * j] 1);}}return ans[n];}
}
