跳石板（动态规划）

一、跳石板

1、题目描述
题目链接

2、题目分析 + 解决

（1）

1. 状态方程：F[ i ]表示跳到 map[ i ]位置所需要的最小步数（-1表示跳不到）
2. 状态转移方程：向前遍历，直接从 j = i - 2开始，map[ j ] 为 -1 的位置跳过，如果 map[ i ] 与 map[ j ] 的差值是 array[ j ] 的约束，F[ i ] = min(F[ j ] + 1，F[ i ])
3. 初始状态：F[ 0 ] = 0，F[ 1 ] = -1
4. 返回结果：返回 F[ len -1 ]
5. 但是这种方法时间复杂度是 O( n^2 )，测试不通过

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int begin = scanner.nextInt();
        int end = scanner.nextInt();
        int len = end - begin + 1;
        int[] map = new int[len];
        
        for (int i = 0; i < len; i++) {
            map[i] = begin++;
        }
        int[] result = new int[len];

        result[0] = 0;
        result[1] = -1;
        for (int i = 2; i < len; i++) {
            for (int j = i - 2; j >= 0; j--) {
                int diffe = map[i] - map[j];
                if(diffe > map[j]/2){
                    break;
                }
                if(map[j] == -1 || map[j] % diffe != 0){
                    continue;
                }
                if(result[i] == 0){
                    result[i] = result[j] + 1;
                } else {
                    result[i] = Math.min(result[j] + 1, result[i]);
                }
            }
            if(result[i] == 0){
                result[i] = -1;
            }
        }

        System.out.println(result[len - 1]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

（2）换种方法

1. 状态方程：F[ i ]表示跳到 map[ i ]位置所需要的最小步数（-1表示跳不到）
2. 状态转移方程：站在 map[ i ] 的位置上（若F[ i ] = -1，跳过这个位置），找到 map[ i ] 的因子（j…），可以得到从 map[ i ] 跳到某些位置（F[ i + j ]…）的步数（F[ i ] + 1）；当F[ i + j ] = -1时，F[ i + j ] = F[ i ] + 1；否则取 min( F[ i ] +1，F[ i + j ] )
3. 初始状态：除 F[ 0 ] = 0，其他位置均为 -1
4. 返回结果：返回 F[ len - 1 ]
5. 时间复杂度：O( n* 根号n )

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int begin = scanner.nextInt();
        int end = scanner.nextInt();
        int len = end - begin + 1;

        int[] map = new int[len];
        for (int i = 0; i < len; i++) {
            map[i] = begin++;
        }

        int[] result = new int[len];
        for (int i = 1; i < len; i++) {
            result[i] = -1;
        }

        for (int i = 0; i < len; i++) {
            // 1. 说明不能跳到这个位置
            if(result[i] == -1){
                continue;
            }
            // 2. 求 map[i] 的因子
            Set<Integer> set = div(map[i]);
            // 3. 更新当前位置所能跳到的位置 的最小步数
            for (int val : set) {
                if(i + val < len){
                    if(result[i + val] == -1){
                        result[i + val] = result[i] + 1;
                    } else {
                        result[i + val] = Math.min(result[i + val], result[i] + 1);
                    }
                }
            }
        }
        System.out.println(result[len - 1]);
    }

    public static Set<Integer> div(int val){
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= Math.sqrt(val); i++) {
            if(val % i == 0 ){
                set.add(i);
                set.add(val / i);
            }
        }
        return set;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

渤海名市，尚武之乡

河北沧州