完全平方数
动态规划
和322零钱兑换完全一致
自己构建完全平方数组，作为价格数组
找到刚好装满背包，但使用金币数量最少的金币数
class Solution { public: int numSquares(int n) { vector<int> sqrt_num; vector<int> dp(n+1,INT_MAX); int tmp = 1; while( pow(tmp,2) <= n ) { sqrt_num.push_back(pow(tmp,2)); tmp++; } dp[0]=0; for(int i=0 ;i<sqrt_num.size();i++) { for(int j=sqrt_num[i] ; j<=n ;j++) dp[j] = min(dp[j] , dp[j-sqrt_num[i]]+1 ); } return dp[n]; } };
二刷
class Solution { public: int numSquares(int n) { vector<int> dp(n+1,INT_MAX); vector<int> nums; for(int i=1 ; (i*i)<=n ; i++) { nums.push_back(i*i); } dp[0] = 0; for(int i=0 ; i<nums.size() ; i++) { for(int j=nums[i] ; j<=n ;j++) { if(dp[j-nums[i]] != INT_MAX) dp[j] = min(dp[j] , dp[j-nums[i]]+1 ); } } return dp[n]; } };
