原题地址

https://leetcode.com/problems/perfect-squares/description/

题意

给定一个数n，求最少要几个平方数（1,4,9,25……）的和能组成这个数

思路

用的是很蠢的办法，没什么思路可言。

坑点

涉及到模运算的时候pow(i,2)要转成int类型的，发现类型转换会对值有影响。。。比如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;
    }
};