题解 | #牛群迁徙# 线性DP

知识点

dp

思路

状态表示 f[i] 表示到达每一个位置的最小步数

状态转移是从f[i] 向每个 f[j] 转移 其中

最后的结果是 f[j]

时间复杂度为

AC code (C++)

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