做网站 中介,网站建设教学设计,海关做预归类的网站,松江新城网站建设目录 题目1- 思路2- 实现⭐完全平方数——题解思路 3- ACM 实现 题目
原题连接#xff1a;279. 完全平方数 1- 思路
思路
动规五部曲 2- 实现
⭐完全平方数——题解思路 class Solution {public int numSquares(int n) {// 1. 定义 dpint[] dp new int[n1];//2. 递推公式… 目录 题目1- 思路2- 实现⭐完全平方数——题解思路 3- ACM 实现 题目
原题连接279. 完全平方数 1- 思路
思路
动规五部曲 2- 实现
⭐完全平方数——题解思路 class Solution {public int numSquares(int n) {// 1. 定义 dpint[] dp new int[n1];//2. 递推公式// dp[j] Math.min(dp[j],dp[j-i*i]1);//3. 初始化int max Integer.MAX_VALUE;for(int i 0 ; i dp.length;i){dp[i] max;}dp[0] 0;for(int i 1 ; i*i n;i){for(int j i*i ; jn ; j){dp[j] Math.min(dp[j],dp[j-i*i]1);}}return dp[n];}
}3- ACM 实现
public class squareNum {public static int numSquares(int n){int[] dp new int[n1];// 2. 递推公式// dp[j] Math.min(j-i*i1,dp[j]);// 3.初始化int MAX Integer.MAX_VALUE;for (int i 0 ; i n;i){dp[i] MAX;}dp[0] 0;//4. 先遍历 物品 后遍历背包for(int i 1; i*i n;i){for(int j i*i ; j n;j){dp[j] Math.min(dp[j - i * i] 1, dp[j]);}}return dp[n];}public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println(输入要求的完全平方数和);int n sc.nextInt();System.out.println(结果是numSquares(n));}
}
