编程题2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            System.out.println(numSquares(n));
        }
    }
    
    private static int numSquares(int n){
        int k = (int)Math.sqrt(n);       // 搜索上界
        int[] dp = new int[n + 1];
        int[] square = new int[k + 1];
        // 存储一些平方数
        for(int i = 1; i <= k; i++)
            square[i] = i * i;
        for(int i = 1; i <= n; i++)
            dp[i] = i;
        for(int i = 2; i < n + 1; i++){
            for(int j = 2; j < k + 1; j++){
                if(square[j] > i) continue;
                if(square[j] <= i) {
                    int index = i / square[j];
                    dp[i] = Math.min(dp[i], dp[i - index * square[j]] + index);
                }
            }
        }
        return dp[n];
    }
}

#include <iostream>
using namespace std;
int Square(int num,int m)
         {
           int num1,min=4;
           if(m==3)
           return 3;
           else
           {
               int i=0;
               m++;
               if(num<1)
               return 0;
               for(int j=1;j*j<num;j++)
               {
                   i=j+1;
               }
               if(i*i==num)
               return 1;
               i--;
               if(i<2)
               return num;
               else
               {
                   for(int j=0;j<(i/2)+1;j++)
                   {
                       num1=num-(i-j)*(i-j);
                       num1=1+Square(num1,m);
                       if(num1<min)
                       min=num1;
                   }
               }
               return min;
           }
       }
int main(){
       int m=0,n;
    cin>>n;
       m=Square(n,m);
    cout<<m;
       return 0;
    }