题解 | #牛牛的跳跃挑战# 线性DP

知识点

动态规划

思路

定义f[i]为到达下标为i位置所需要的最小的代价, 答案为f[n]

每一次可以从前面3个位置进行转移

时间复杂度

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    const int INF = 1e9;
    int minEnergyJump(vector<int>& height) {
        int n = height.size();
        vector<int> f(n + 1, INF);
        f[0] = f[1] = f[2] = 0;
        for (int i = 3; i <= n; i ++) {
            for (int j = max(0, i - 3); j < i; j ++) {
                f[i] = min(f[i], f[j] + height[j]);
            }
        }
        return f[n];
    }
};