ac

常规动态规划

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        for(int i=1;i<n;i++){
            int minStep = Integer.MAX_VALUE;
            // 前面的位置都可能到达位置i
            for(int j=0;j<i;j++){
                if(j + arr[j] >= i){
                    minStep = Math.min(minStep, dp[j] + 1);
                }
            }
            dp[i] = minStep;
        }
        int ans = dp[n-1];
        System.out.println(ans);
    }

}
/*
6
3 2 3 1 1 4

2

arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。
 */

当i < j 的时候，一定有dp[i] < dp[j]，即前面位置的走到所需要的步数肯定小于后面的位置，因为
arr[i]==k代表可以从位置向右跳1~k个距离。比如，arr[2]==3,代表可以从位置2跳到位置3、位置4或位置5。

只要找到一个就可以退出了，后面的比较都是浪费的

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        for(int i=1;i<n;i++){
            int minStep = Integer.MAX_VALUE;
            // 前面的位置都可能到达位置i
            for(int j=0;j<i;j++){
                if(j + arr[j] >= i){
                    minStep = Math.min(minStep, dp[j] + 1);
                    break;
                }
            }
            dp[i] = minStep;
        }
        int ans = dp[n-1];
        System.out.println(ans);
    }

}
/*
6
3 2 3 1 1 4

2

arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。
 */

ac (四边形定理：时间复杂度降低一个数量级)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        int[] cands = new int[n];
        for(int i=1;i<n;i++){
            int minStep = Integer.MAX_VALUE;
            int pos = -1;
            // 前面的位置都可能到达位置i
            for(int j=cands[i-1];j<i;j++){
                if(j + arr[j] >= i){
                    minStep = Math.min(minStep, dp[j] + 1);
                    pos = j;
                    break;
                }
            }
            dp[i] = minStep;
            cands[i] = pos;
        }
        int ans = dp[n-1];
        System.out.println(ans);
    }

}
/*
6
3 2 3 1 1 4

2

arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。
 */

最优解

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int step = 0;
        int cur = 0; // 当前用step步数能走到的最远位置
        int next = arr[0];
        for(int i=1;i<n;i++){
            if(cur < i){
                // 必须多走一步
                step++;
                cur = next;
            }
            // 对每个i，都求了一次能到达都最远位置
            next = Math.max(next, i + arr[i]);
        }
        int ans = step;
        System.out.println(ans);
    }
}
/*
6
3 2 3 1 1 4

2

arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。
 */