题目链接：https://vjudge.net/problem/UVA-11384
题意：给定正整数 n，用最少的操作把序列 1,2，，，n 全部变成 0；
操作是：每次可以从序列中选择一个或者多个，同时减去一个相同的数。
其实是一个递归分治的思想，把一部分数字选出来，同时一减，结果就变成了前面没有减过的了，数量不影响结果，反正可以一次拿出很多来操作。
那么怎么选择，使得 n 到 x 的时候 x 最小呢？
经过尝试，发现，减后面一半是最好的，f(n) = f(n/2) + 1;
f(1) = 1;
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int dp(int n) { 6 if(n==1) 7 return 1; 8 else return dp(n/2) + 1; 9 } 10 11 int main() 12 { 13 int n; 14 while(scanf("%d",&n)!=EOF) { 15 printf("%d\n",dp(n)); 16 } 17 return 0; 18 }
原文：http://www.cnblogs.com/TreeDream/p/6701560.html
