题解（动态规划）

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const int N = 3e5 + 20;
const int INF = 0x3f3f3f3f;
const LL INFLL =0x3f3f3f3f3f3f3f3f;
int dp[N]; // 在第i的距离，所需要花费的最少时间
void so() {
		int n;
		cin >> n;
		n--;
		for(int i = 1 ; i <= n ; i++ ) dp[i] = dp[i - 1] + 1; //每一步正常走1米
		for(int i = 1; i <= n ; i++ ){
			for(int j = 1 ; j * j <= i ; j++ ){ //弹射距离，j*j ，必须要小于i，也就是从i - j * j 的地方，跳 j * j 的距离刚好跳到距离i的地方。
				dp[i] = min(dp[i] , dp[i - j * j] + j + 1); // 从 i - j * j 的地方弹射过来，时间是j + 1.
			}
		}
		cout <<dp[n];
		
}
int main() {
    IOS
    int tt=1;
  //  cin >> tt;
    while (tt--)
    so();
}