代码如下：（直接暴力dp）

#include"bits/stdc++.h"
using namespace std;
int a[1000001];
void dp(int s)
{
	if (s%2==1)
	{
	   a[s]=a[(s-1)]+1;
	   return;
	}
	a[s]=min(a[(s-1)],a[(s/2)])+1;
}
int main()
{
	int n;
	scanf("%d",&n);
	a[n]=1;
	if (n==1)
	{
		printf("1");
		return 0;
	}
	for (int i=2;i<=n;i++)
	{
		dp(i);
	}
	printf("%d",a[n]);
	return 0;
}