先看题目：https://ac.nowcoder.com/acm/contest/5968/A
题目描述：
有n级台阶，在i级台阶可以走到i+1级台阶(仅h[i+1] == h[i]+1)时，也可以往下一级台阶到i-1级。如果连续下降k级台阶到达了第i级台阶可以上升到高度小于等于h[i]+2^k的任何一个位置。
解题思路：
定义状态f[i]为到达i级台阶的最小步数，枚举i,j,代表从某个台阶向下k级到达j级，k可以由ceil(log2(a[i]-a[j]))来求出，如果j+k < i，那么可以更新f[i]。为什么不再去考虑是向下走k+1级，k+2级...到达j的呢？这是因为f[i]一定是非递减的。因此f[j+k]+k+1肯定更优于f[j+k+1]+k+1+1...

你看，n^2dp就轻松解决啦，所幸有师哥的方法指导，否则脑残的我还在记忆化搜索debug。。。反思一下，这题为什么能for循环dp呢，虽然题目中说了可以从i+1级台阶下到i级台阶，但是完全没有必要啊...都已经能上到i+1了，当然也能到直接上到i了，完全不需要再‘绕路’，因此f[i]只需要由前面的更新得来。
代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int dp[210];
int a[210];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp, inf, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }
    dp[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j < i; j++)
        {
            int k = ceil(log2(a[i]-a[j]));
            if(j+k < i) dp[i] = min(dp[i], dp[j+k]+k+1);
        }
    }
    printf("%d\n",dp[n] == inf ? -1 : dp[n]);
}