性能测试概念
294 2023-04-03 05:11:47
给你一个整数n,返回和为n的完全平方数的最少数量 。
完全平方数是一个整数,其值等于另一个整数的平方,换句话说,其值等于一个整数自乘的积。
例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
思路:
回溯法常用来遍历输出全部路径,以及解决可达性问题
对于这种最优问题,考虑使用动态规划,核心思想是用空间换时间
dp[i]状态表示为整数i的完全平方数最少数量
状态转移方程dp[i] = min(dp[i-j*j])+1
边界条件:dp[0] =0
class Solution {public: int numSquares(int n) { vector<int> dp(n+1); for(int i=1;i<=n;i++){ int min_=INT_MAX; for(int j=1;j*j<=i;j++){ min_=min(min_,dp[i-j*j]); } dp[i]=min_+1; } return dp[n]; }};