题解 | #不能连续吃草的牛# 状态机DP

知识点

状态机DP

思路

状态表示: f[i][j] 表示前i个位置且第i个位置 取/不取的状态为j的最大值

状态转移:

f[i][0] = max(f[i-1][0], f[i-1][1])

f[i][1] = f[i-1][0] + nums[i-1](下标从0开始)

时间复杂度

AC Code (C++)

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