原題地址
https://leetcode.com/problems/perfect-squares/description/
題意
給定一個(gè)數(shù)n妈经，求最少要幾個(gè)平方數(shù)（1,4,9,25……）的和能組成這個(gè)數(shù)
思路
用的是很蠢的辦法纲堵，沒什么思路可言言沐。
坑點(diǎn)
涉及到模運(yùn)算的時(shí)候pow(i,2)要轉(zhuǎn)成int類型的鸭栖，發(fā)現(xiàn)類型轉(zhuǎn)換會(huì)對(duì)值有影響秩霍。款违。蛉拙。比如pow(5,2)=25，可是(int)pow(5,2)就等于24了觉增。兵拢。。
代碼
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
class Solution {
public:
int minForSome(vector<vector<int> > &vec, int cur, int sum) {
int min = sum;
for (int i = 1; i < cur; i++) {
if (vec[i][sum] != 0 && vec[i][sum] < min) {
min = vec[i][sum];
}
}
return min;
}
int numSquares(int n) {
int m = sqrt(n) + 1;
int pre[n + 1];
for (int i = 0; i <= n; i++) {
pre[i] = i;
}
vector<vector<int> > vec(m + 1, vector<int>(n + 1, -1));
for (int i = 1; i < m + 1; i++) {
vec[i][0] = 0;
}
for (int i = 1; i < n + 1; i++) {
vec[1][i] = i;
}
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ((int)pow(i, 2) > j) {
vec[i][j] = 0;
} else {
vec[i][j] = minForSome(vec, i, j % (i*i))+ j / (i*i);
if (i == 5 && j == 43) {
}
}
}
}
int min = n;
for (int i = 1; i <= m; i++) {
if (vec[i][n] < min && vec[i][n] != 0) {
min = vec[i][n];
}
}
return min;
}
};
