$20$ 分code:

#include<bits/stdc++.h>
using namespace std;
int n; 
int dp[1000010];
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
	    if(i%2==0)
			dp[i]=min(dp[i-1]+1,dp[i/2]+1);
		else 
			dp[i]=dp[i-1]+1;
	}
	cout<<dp[n];
	return 0;
}

第九行我把 $+1$ 提到了 $\min$ 里面，我以为都一样，但一看 $\text{WA}$ 声一片。

$\text{AC}$ codc:

#include<bits/stdc++.h>
using namespace std;
int n; 
int dp[1000010];
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
	    if(i%2==0)
			dp[i]=min(dp[i-1],dp[i/2])+1;
		else 
			dp[i]=dp[i-1]+1;
	}
	cout<<dp[n];
	return 0;
}

有大佬知道这是为什么嘛awa