题解 | 买苹果

import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        int arr[] = new int[n + 1];
        for (int i = 1; i < n + 1; i++) arr[i] = Integer.MAX_VALUE;
        int hasDone[] = new int[n + 1];
        boolean canGo = true;
        while (canGo) {
            canGo = false;
            for (int i = 0; i < n + 1; i++) {
                if (arr[i] != Integer.MAX_VALUE && hasDone[i] == 0) {
                    if (i + 6 <= n){
                        arr[i + 6] = Math.min(arr[i + 6], arr[i] + 1);
                        canGo = true;
                    }
                    if (i + 8 <= n){
                        arr[i + 8] = Math.min(arr[i + 8], arr[i] + 1);
                        canGo = true;
                    }
                    hasDone[i] = 1;
                }
            }
        }
        // System.out.println(Arrays.toString(arr));
        // System.out.println(Arrays.toString(hasDone));
        if(arr[n]==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(arr[n]);
    }
}

dp：要点是用数组arr存当前苹果数（下标）对应的最少袋数，用另一个数组hasDone存是否遍历过的状态（即是否用当前苹果数+6/+8过）

遍历：去遍历当前没有遍历过的袋数，比如12个苹果，12+6=18，则标记18个苹果的位置已经遍历过，并维护18个苹果对应的最少袋数；12+8=20，则标记20个苹果的位置已经遍历过，并维护20个苹果对应的最少袋数。依次循环，没次都从0~n遍历