滑动窗口算法可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

参考文章：

【算法】动态规划

【算法】备忘录法（记忆化搜索）

【算法】动态规划（Dynamic Programming）

动态规划详解

动态规划（Dynamic Programming，简称DP）是一种广泛应用于数学、计算机科学和经济学等领域的方法论。其核心思想是通过将复杂问题分解为相对简单的子问题，并存储子问题的解以避免冗余计算，从而显著提高计算效率。

动态规划作为运筹学的一个分支，专注于解决决策过程的最优化问题。20世纪50年代初，美国数学家贝尔曼（R. Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，并基于此创立了动态规划。动态规划的应用范围极为广泛，包括工程技术、经济、工业生产、军事以及自动化控制等多个领域。在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等实际问题中，动态规划均展现出了显著的效果。

算法思想

动态规划常常适用于具有重叠子问题和最优子结构性质的问题。其基本思想是将待求解的问题分解为若干个相关联的子问题，先求解子问题，然后利用这些子问题的解来构造原问题的解。对于重复出现的子问题，只在第一次遇到的时候对他进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

总体思想
（1）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
（2）经分解得到的子问题往往不是互相独立的，有些子问题被重复计算多次
（3）若能保存已解决子问题的答案，而在需要时再找出已求得的答案，就可避免大量重复计算，从而得到多项式时间算法（备忘录法）

动态规划的基本过程包括定义子问题，解决子问题，合并子问题的解来求解原问题。动态规划通常采用自底向上的方式进行，通过迭代计算子问题并存储子问题的解，逐步求解更大规模的问题，直到求解出原问题。

动态规划主要包括两个要素：最优子结构和重叠子问题。

重复子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质
动态规划算法对每个子问题只解一次，并将其解保存在一个表格中，当再次需要解此子问题时，只是简单用常数时间查看一下结果
通常不同的子问题个数随问题的大小呈多项式增长，用动态规划算法只需要多项式时间，从而获得较高的解题效率

最优子结构

一个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质
分析问题的最优子结构性质：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解
最优子结构是一个问题能用动态规划算法求解的前提

动态规划算法与分治算法的异同点

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
分治算法经分解得到的子问题往往是独立的
动态规划算法经分解得到的子问题往往不是独立的，有些子问题被重复计算多次

动态规划求解的基本步骤

找出最优解的性质，并刻划其结构特征
递归地定义最优值
以自底向上的方式计算出最优值
根据计算最优值时得到的信息，构造最优解

算法步骤

动态规划算法的基本步骤通常包括：划分阶段、定义状态、建立状态转移方程以及确定边界条件等。

划分阶段：按照时间或空间特征，将问题划分为若干个阶段，每个阶段对应一个决策过程。这些阶段需要满足无后效性，即某个阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。这是动态规划方法应用的前提，也是保证算法有效性的基础。

定义状态：对每个阶段定义状态变量，状态变量应该能够表示出该阶段所有可能的信息，且能从中推导出下一阶段的状态。在定义状态时，要考虑到问题的具体特征，使得状态变量能够简洁明了地反映问题的本质。

状态转移方程：根据问题的性质，建立从一个阶段到下一个阶段的递推关系式，即状态转移方程。状态转移方程是动态规划算法的核心部分，它描述了问题在不同阶段之间的转移关系。在建立状态转移方程时，需要仔细分析问题的特征，找到正确的状态转移方式。同时，要注意避免重复计算，提高算法的效率。

边界条件：确定状态转移方程中的起始状态，即问题的初始条件。边界条件是动态规划算法的重要组成部分，它决定了算法的起点和范围。在确定边界条件时，要根据问题的具体要求进行设定，确保算法的正确性和有效性。

求解最优解：利用状态转移方程和边界条件，从初始状态开始逐步求解问题，最终得到问题的最优解。在求解过程中，要注意保存中间结果，以便后续使用。同时，要注意算法的时间复杂度和空间复杂度，确保算法在实际应用中的可行性。

优化与改进：在得到基本解决方案后，可以对算法进行优化和改进。例如，可以采用更高效的数据结构来存储中间结果，或者采用更合理的状态转移方式来减少计算量。此外，还可以结合其他算法和技术来进一步提高算法的性能和适用范围。

算法实现与测试：将优化后的算法用具体的编程语言实现，并进行测试以验证其正确性和有效性。在实现过程中，要注意代码的可读性和可维护性，以便后续修改和扩展。同时，要进行充分的测试以确保算法在各种情况下的正确性。

动态规划优缺点

优点

对于具有重叠子问题和最优子结构性质的问题，动态规划可以显著提高求解效率，避免不必要的重复计算。通过存储和复用子问题的解，动态规划算法能够避免重复计算相同的子问题，从而大大减少计算量。
动态规划算法的代码通常比较简洁，易于理解和实现。一旦确定了问题的状态转移方程和边界条件，动态规划算法的代码实现往往非常直观和简洁。

缺点

对于没有重叠子问题和最优子结构性质的问题，动态规划算法可能并不适用，此时需要考虑其他算法。动态规划算法的有效性建立在问题的重叠子问题和最优子结构性质上，如果问题不具备这些性质，那么动态规划算法就无法发挥其优势。
动态规划算法的空间复杂度通常较高，需要存储所有子问题的解，以便后续使用。这可能导致算法在处理大规模问题时需要消耗大量的内存空间。在某些情况下，可能需要考虑使用滚动数组或其他优化技巧来降低空间复杂度。滚动数组是一种常用的优化方法，它只保留当前需要使用的子问题解，从而避免了存储所有子问题的解。

应用场景

动态规划是求多阶段决策过程最优化的一种数学方法，它将问题的整体按时间或空间的特征分成若干个前后衔接的时空阶段，把多个阶段决策问题表示为前后有关的一系列单阶段决策问题，然后逐个求解，从而求出整个问题的最有决策序列。动态规划的十大经典问题：

最长公共子序列

背包问题

矩阵链路乘法

编辑距离

硬币找零问题

最大子段和

最长递增子序列

0-1背包问题

划分问题

合并排序问题

数字三角形

有一只小兔子站在一片三角形的胡萝卜地的入口（数字1处），如下所示，图中的数字表示每一个坑中胡萝卜的数量，小兔子每次只能跳到左下角或者右下角的坑中，请问小兔子怎么跳才能得到最多数量的胡萝卜？

1
3 2
4 10 1
4 3 2 20

经典递归解法

采用暴力法解决这个问题，从第一层开始，每次有两个选择，左下角和右下角，也就是n层的话，有2^{n-1}条路径，T（n） = 2^n 。

代码实现思路

把上面的三角形放到一个二维数组中，没有放数的地方都为0
从二位数组的a[i][j] 开始，最多的胡萝卜数为a[i][j]加上以右下角为起点和左下角为起点路径中的胡萝卜最大数的路径，循坏递归，因为每个点都有两条路径选择，每次选择路径中胡萝卜最多的路径。递归的结束条件是 i = n+1时结束，因为有n层，到n+1层时自然就结束。

代码实现

public static void main(String[] args) {
    int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};
    System.out.println(solve(a,0,0));
}
// 递归
public static int solve(int[][] a,int i,int j){
    // 第 n+1 层结束  ===》从0层开始计算 ，那么 i = n 时结束
    if (i == a.length){
        return 0;
    }
    return a[i][j]+ Math.max(solve(a,i+1,j),solve(a,i+1,j+1));
}

备忘录法

什么是备忘录法

备忘录法是为了解决避免递归算法中相同子问题的重复求解。
备忘录法为每个解过的子问题建立备忘录以备需要时查看，所以也称搜表法。
备忘录法的控制与直接使用递归方法的控制结构相同。
备忘录法又称记忆化搜索，自顶向下的方式解决问题。

备忘录法的实现

避免子问题重复被求解，可以定义一个数组，每次要计算一个子问题时，首先从数组中查询这个子问题的解，子问题解没有在数组中，说明没有计算过该子问题，那么计算该子问题，并将解放到数组中去，以便下次计算该子问题时，可以直接从数组中拿。

代码实现

上面递归时候，我们solve(a,2,1)被重复计算过两次。此时可用备忘录法，即利用一个二维数组记录每次子问题计算的值（例如a(6，3)的解就放到 d [6] [3]中），每次需要计算子问题时，先判断数组中是否计算过保存了，有则直接取用，没有就计算并把结果保存到数组中。

public static void main(String[] args) {
    int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};
    System.out.println(solve(a, 0, 0, new int[a.length][a.length]));
}
public static int solve(int[][] a,int i,int j,int[][] p){
    //第 n+1 层结束  ===》从0层开始计算 ，那么 i = n 时结束
    if (i == a.length){
        return 0;
    }
    if (p[i][j] == 0) {
        p[i][j] = a[i][j] + Math.max(solve(a, i + 1, j, p), solve(a, i + 1, j + 1, p));
    }
    return p[i][j];
}

动态规划

思路一

p[i][j]表示(i, j)的达到最后一层的最大路径和，那么p[i][j]的最优解包含了子问题p[i+1][j]或p[i+1][j+1]的最优解
状态转移方程（递归方程）及图解
最终结果是p[0][0]（从表的最后一层开始填）
动态规划法又叫填表法，填完上面那张表结果就出来了

代码实现：

public static void main(String[] args) {
    int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};
    System.out.println(solve(a));
}
public static int solve(int[][] a){
    int[][] p = a.clone();
    // 最后一层的数不需要修改 ，从倒数第二次开始
    for (int i = a.length - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            p[i][j] = a[i][j] + Math.max(p[i+1][j],p[i+1][j+1]);
        }
    }
    return p[0][0];
}

思路二

p[i][j]表示从(1,1)到达(i, j) 的最大路径和，那么p[i][j]的最优解包含了子问题p[i-1][j-1]或p[i-1][j]的最优解
状态转移方程（递归方程）和图解
最终结果是p[4][4]（从表的第一层开始填）

最长公共子序列（LCS）

基本概念

最长公共子序列（Longest Common Subsequence，简称LCS）。其基本思想是寻找两个字符串中都存在的最长子序列，该最长子序列可以不连续，但要保证其相对顺序一样。（注意，这里是子序列，而不是子串，子序列可以不连续，而子串是连续的）。具有特征如下：

长度：最长公共子序列的长度最大为两个序列的最小长度，如果两个序列完全相同，则它们的最长公共子序列即为它们本身。

顺序：最长公共子序列中的子序列在原序列中的顺序一致。

相同元素：最长公共子序列中的子序列所包含的元素必须在两个原序列中都存在。

不连续性：最长公共子序列不需要在原序列中连续出现。

动态规划

求解LCS问题，不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列，它的时间复杂度是指数阶，太恐怖了。解决LCS问题，需要借助动态规划的思想。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

特征分析

设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：

如果am=bn，则zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列；
如果am!=bn，则若zk!=am，蕴涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；
如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一个最长公共子序列。

案例说明：S1 = {1,3,4,5,6,7,7,8} 和 S2 = {3,5,7,4,8,6,7,8,2}），结合上图：
假如S1的最后一个元素与 S2的最后一个元素相等，那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。

假如S1的最后一个元素与 S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的LCS就等于： {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

递归公式

根据LCS的特征，假设需要求 a1 … am 和 b1 … b(n-1)的LCS 和 a1 … a(m-1) 和 b1 … bn的LCS，一定会递归地并且重复地把如a1… a(m-1) 与 b1 … b(n-1) 的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果，避免重复计算。

假设用c[i,j]表示Xi 和 Yj 的LCS的长度（直接保存最长公共子序列的中间结果不现实，需要先借助LCS的长度）。其中X = {x1 … xm}，Y ={y1…yn}，Xi = {x1 … xi}，Yj={y1… yj}。可得递归公式如下：

计算LSC的长度

以表格的形式表示整个过程如下：

下标	j	0	1	2	3	4	5	6	7	8	9
i		S2j	3	5	7	4	8	6	7	8	2
0	S1i	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0	0	0
2	3	0	1	1	1	1	1	1	1	1	1
3	4	0	1	1	1	2	2	2	2	2	2
4	5	0	1	2	2	2	2	2	2	2	2
5	6	0	1	2	2	2	2	3	3	3	3
6	7	0	1	2	3	3	3	3	4	4	4
7	7	0	1	2	3	3	3	3	4	4	4
8	8	0	1	2	3	3	4	4	4	5	5

填表的过程就相当于解题的过程（第0行、第0列初始值都为0），以第0行为参照，先从左到右填满第1行；再以第1行为参照，从左到右填满第2行；以此类推，当表格填完后，答案就出来了（即为L[n][n]）。根据性质，c[8,9] = S1 和 S2 的 LCS的长度，即为5。

实现代码

参见下文最长公共子序列

0-1背包问题

问题描述

给定n种物品（每种物品只有一件）和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
对于每种物品，只有两种选择：装(1)或者不装(0)，不允许装物品的一部分

动态规划

n=5, c=10, w={2, 2, 6, 5, 4}, v={6, 3, 5, 4, 6}
选中1，2，5三件物品，最高价值15，总重8
填表，物品的种类为表行，背包容量+1为行，从后面填到前面，j表示背包容量。
最后一行
前面的行
最大值为右上角

代码实现一

public static void main(String[] args) {
    // 浪费数组的第一个
    int[] w = {0,2, 2, 6, 5, 4};
    int[] v = {0,6, 3, 5, 4, 6};
    System.out.println(fun(5, 10, v, w));
}
public static int fun(int n,int c,int[] v,int[] w){
    int[][] m = new int[n+1][c+1];
    // 防止数组越界
    int jMax = Math.min(w[n]-1,c);
    // Step1:填最后一行
    // j<w[n] ==>m[n][j]=0
    for (int j = 0; j <= jMax; j++) {
        m[n][j] = 0;
    }
    // j>=w[n] ==>m[n][j]=v[n]
    for (int j = w[n]; j <= c; j++) {
        m[n][j] = v[n];
    }
    // Step2: 从倒数第二行往前面填
    for (int i = n-1; i > 1; i--) {
        jMax = Math.min(w[i]-1,c);
        for (int j = 0; j <= jMax; j++) {
            m[i][j] = m[i+1][j];
        }
        for (int j = w[i]; j <= c; j++) {
            m[i][j] = Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
        }
    }
    //第一行最后一个元素
    m[1][c] = m[2][c];
    if (c >= w[1]){
        m[1][c] = Math.max(m[1][c],m[2][c-w[1]]+v[1]);
    }
    return m[1][c];
}

代码实现二

知道选择了哪些物品使得价值最大，选择了物品用1表示，没选择用0表示：

// 根据填的表格推断
public static void traceback(int[][] m,int n,int c,int[] w){
    int[] x = new int[n+1];
    for (int i = 1; i < n; i++) {
        //没有选择
        if (m[i][c] == m[i+1][c] ){
            x[i] = 0;
        }else {
            x[i] = 1;
            c -= w[i];
        }
    }
    x[n] = (m[n][c]>0) ? 1:0;
    for (int i =1 ; i < x.length; i++) {
        System.out.print(x[i]+" ");
    }
    System.out.println();
}

算法题

正则表达式匹配

LeetCode 10 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符

'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

示例 1：
1
2
3
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
1
2
3
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
1
2
3
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：

1 <= s.length <= 20，1 <= p.length <= 20

s 只包含从 a-z 的小写字母。

p 只包含从 a-z 的小写字母，以及字符 . 和 *。

保证每次出现字符 * 时，前面都匹配到有效的字符

public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();
    boolean[][] memory = new boolean[sLen+1][pLen+1]; // i,j是否匹配
    memory[0][0] = true;
    for(int i = 0; i <= sLen; i++) {
        for(int j = 1; j <= pLen; j++) {
            if(p.charAt(j-1) == '*') { // 用例保证了第一个字符不可能是 *
                memory[i][j] = memory[i][j-2] || 
                    (i > 0 && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && memory[i-1][j]);
            } else {
                memory[i][j] = i > 0 && 
                    (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.') && memory[i-1][j-1];
            }
        }
    }
    return memory[sLen][pLen];
}

最大子数组和

LeetCode 53 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：
1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
1
2
输入：nums = [1]
输出：1
示例 3：
1
2
输入：nums = [5,4,-1,7,8]
输出：23
提示：

1 <= nums.length <= 105

-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = 0;
    for (int num : nums) {
        if (sum > 0) sum += num;
        else sum = num;
        res = Math.max(res, sum);
    }
    return res;
}

最长公共子序列

LeetCode 1143 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
1
2
3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：

1 <= text1.length, text2.length <= 1000

text1 和 text2 仅由小写英文字符组成。

public int longestCommonSubsequence(String text1, String text2) {
    // 定义dp[i][j]表示[0,i-1]的子串text1与[0,j-1]的子串text2的最长公共长度
    // 假如两者text1[i]=text2[j]，当前长度就是dp[i-1][j-1]+1
    // 假如两者不等，当前长度可以从[i-1][j]推出，也可以从[i][j-1]推出
    // 当前值可以从左上角、左边、上方3个方向推导
    int n1 = text1.length();
    int n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for(int i = 1; i <= n1; i++) {
        for(int j = 1; j <= n2; j++) {
            if(text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[i][j] = dp[i -1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n1][n2];
}

找终点

牛客网_找终点

给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。要求:
1、第一步必须从第一元素开始，且1<=第一步的步长<len/2;(len为数组的长度，需要自行解析)。
2、从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少,如果目标不可达返回-1，只输出最少的步骤数量。
3、只能向数组的尾部走，不能往回走。
输入描述：由正整数组成的数组，以空格分隔， 数组长度 小于100，请自行解析数据数量。
输出描述：正整数，表示最少的步数，如果不存在输出-1
示例1
输入 7 5 9 4 2 6 8 3 5 4 3 9
输出  2
说明：
第一步:第一个可选步长选择2，从第一个成员7开始走2步，到达9;
第二步:从9开始，经过自身数字9对应的9个成员到最后。
示例2
输入 1 2 3 7 1 5 9 3 2 1
输出 -1

public static void findTheEnd(int n, int[] a) {
    // 初始化动态规划数组，dp[i]表示到达第i个位置所需的最少步骤数
    int[] dp = new int[n];
    Arrays.fill(dp, 999999); // 初始化填充较大值
    dp[0] = 0; // 第一个位置的步骤数为0
    for (int i = 1; i < n / 2; i++) { // 初始化从第一个位置开始的步长，步长范围为1到len/2
        dp[i] = 1;
    }
    // 遍历数组，更新动态规划数组
    for (int i = 1; i < n; i++) {
        if (i + a[i] >= n) {
            continue;
        }
        dp[i + a[i]] = Math.min(dp[i + a[i]], dp[i] + 1);
    }
    // 输出结果，如果最后一个位置的步数仍为无穷大，表示不可达，输出-1
    System.out.println(dp[n - 1] == 999999 ? -1 : dp[n - 1]);
}

或者

public class StepTo {
    static Input input;
    static {
        input = new Input("7 5 9 4 2 6 8 3 5 4 3 9");
        input = new Input("1 2 3 7 1 5 9 3 2 1");
    }
    public static void main(String[] args) {
        int steps = 1000;
        String[] split = input.nextLine().split(" ");
        int[] array = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            array[i] = Integer.parseInt(split[i]);
        }
        // 如果最后一脚 迈到终点 则说明该这一步的起脚点 下标 + 对应的之恰好是中调的坐标
        // 依次递归个逻辑即可找到路径 计算该路径的步数即可
        for (int i = array.length - 2; i > 0; i--) {
            if (array[i] + i == array.length - 1) {
                int steps1 = getSteps(array, i);
                if (steps1 > 0) {
                    steps = Math.min(steps, i);
                }
            }
        }
        if (steps == 1000) {
            System.out.println(-1);
        } else {
            System.out.println(steps);
        }
    }
    public static int getSteps(int[] array, int step) {
        // 如果这一步落在数组的前半部分， 第一步迈到这里即可以到达终点
        if ( step >= 1 && step < (array.length - 1)/2) {
            return 2;
        }
        // 如果起脚点小于 1 说明没有合适的起脚点
        if (step < 1) {
            return -1000;
        }
        int nextStep = -1000;
        // 找到上一脚的起脚点
        for (int i = step - 1; i > 0; i--) {
            if (array[i] + i == step) {
                nextStep = i;
            }
        }
        return  getSteps(array, nextStep) + 1;
    }
}

下标	j	0	1	2	3	4	5	6	7	8	9
i		S2j	3	5	7	4	8	6	7	8	2
0	S1i	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0	0	0
2	3	0	1	1	1	1	1	1	1	1	1
3	4	0	1	1	1	2	2	2	2	2	2
4	5	0	1	2	2	2	2	2	2	2	2
5	6	0	1	2	2	2	2	3	3	3	3
6	7	0	1	2	3	3	3	3	4	4	4
7	7	0	1	2	3	3	3	3	4	4	4
8	8	0	1	2	3	3	4	4	4	5	5

下标	j	0	1	2	3	4	5	6	7	8	9
i		S2j	3	5	7	4	8	6	7	8	2
0	S1i	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0	0	0
2	3	0	1	1	1	1	1	1	1	1	1
3	4	0	1	1	1	2	2	2	2	2	2
4	5	0	1	2	2	2	2	2	2	2	2
5	6	0	1	2	2	2	2	3	3	3	3
6	7	0	1	2	3	3	3	3	4	4	4
7	7	0	1	2	3	3	3	3	4	4	4
8	8	0	1	2	3	3	4	4	4	5	5

下标	j	0	1	2	3	4	5	6	7	8	9
i		S2j	3	5	7	4	8	6	7	8	2
0	S1i	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0	0	0
2	3	0	1	1	1	1	1	1	1	1	1
3	4	0	1	1	1	2	2	2	2	2	2
4	5	0	1	2	2	2	2	2	2	2	2
5	6	0	1	2	2	2	2	3	3	3	3
6	7	0	1	2	3	3	3	3	4	4	4
7	7	0	1	2	3	3	3	3	4	4	4
8	8	0	1	2	3	3	4	4	4	5	5