题目描述
机器猫要在电脑前打字。一共需要打 nn 个字，但现在文档里只有一个字。
机器猫有两种操作可以做。假设现在已经有 xx 个字，机器猫可以选择：
- 往文档最后加一个字。字数变成 x+1x+1。
- 把文档复制粘贴一遍。字数变成 2x2x。
问机器猫至少需要多少次操作，才能得到恰好 nn 个字。
输入格式
仅一行，一个正整数 nn。
输出格式
仅一行，一个正整数，表示最少操作次数。
输入输出样例
输入 #1复制
16
输出 #1复制
4
输入 #2复制
5
输出 #2复制
3
说明/提示
样例解释
样例数据1，1→2→4→8→161→2→4→8→16，共 4 步。
样例数据2，1→2→4→51→2→4→5，共 3 步。
数据规模与约定
对于 100%100% 的数据，n≤106n≤106。
代码：
C++：
#include<iostream>
#include<cmath>
using namespace std;
const int N = 0x3f3f3f;
long long dp[N];
int main() {int n; cin >> n;dp[1] = 0;dp[2] = 1;if (n == 1) {cout << dp[1] << endl;}else if (n == 2) {cout << dp[2] << endl;}else {for (int i = 3; 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] << endl;}return 0;
}Python：
n = int(input())
N = 1000001
dp = [0] * N
dp[1] = 0
dp[2] = 1
if n == 1:print(dp[1])
elif n == 2:print(dp[2])
else:for i in range(3, n + 1, 1):if i % 2 == 0:dp[i] = min(dp[i - 1], dp[int(i / 2)]) + 1else:dp[i] = dp[i - 1] + 1print(dp[n])Java：
package com.my.gududu;import java.util.*;public class dadada{public static void main(String[] args) {int N = 1000001;long dp[] = new long[N];Scanner input = new Scanner(System.in);int n = input.nextInt();dp[1] = 0;dp[2] = 1;if (n == 1) {System.out.println(dp[n]);}else if (n == 2) {System.out.println(dp[n]);}else {for (int i = 3; i <= n; i++) {if (i % 2 == 0) {dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;}else {dp[i] = dp[i - 1] + 1;}}System.out.println(dp[n]);}}
}
