private int f(int i, boolean isLimit, boolean isNum) {
    if (i == s.length) return isNum ? 1 : 0; // 如果填了数字，则为 1 种合法方案
    if (!isLimit && isNum && dp[i] >= 0) return dp[i]; // 在不受到任何约束的情况下，返回记录的结果，避免重复运算
    var res = 0;
    if (!isNum) // 前面不填数字，那么可以跳过当前数位，也不填数字
        // isLimit 改为 false，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束
        // isNum 仍然为 false，因为没有填任何数字
        res = f(i + 1, false, false);
    var up = isLimit ? s[i] : '9'; // 根据是否受到约束，决定可以填的数字的上限
    // 注意：对于一般的题目而言，如果此时 isNum 为 false，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况
    for (var d : digits) { // 枚举要填入的数字 d
        if (d.charAt(0) > up) break; // d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环
        // isLimit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束
        // isNum 为 true，因为填了数字
        res += f(i + 1, isLimit && d.charAt(0) == up, true);
    }
    if (!isLimit && isNum) dp[i] = res; // 在不受到任何约束的情况下，记录结果
    return res;
}

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][][] dp = new int[n][n][2];
        for (int len=1;len<=n;len++) {
            for (int i = 0;i < n;i++) {
                int j = i + len-1;
                if (j >= n) {
                    continue;
                }
                int p1 = piles[i];
                int p2 = piles[j];
                if (len == 1) {
                    dp[i][j][0] = p1;
                    dp[i][j][1] = -p1;
                    continue;
                }

                dp[i][j][0] =  Math.max(p1 + dp[i+1][j][1], p2
                 + dp[i][j-1][1]);
                
                dp[i][j][1] = Math.min(-p1 + dp[i+1][j][0], -p2 + dp[i][j-1][0]);
            }
        }

        return dp[0][n-1][0] > 0;
    }
}

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int left = 0;
        int needMin = 0;
        int count = 0;
        for (int r = left;r<arr.length;r++) {
            if (isValid(arr, left, r, needMin)) {
                count++;
                left = r+1;
                needMin = r + 1;
            }
        }
        return count;
    }

    public boolean isValid(int[] arr, int left ,int right , int needMin) {
        int[] newa = new int[right -left + 1];
        boolean found = false;
        for (int i = 0; i < newa.length;i++) {
            newa[i] = arr[left + i];
            if (needMin == newa[i]) {
                found = true;
            }
        }
        Arrays.sort(newa);
        for (int i = 1; i < newa.length;i++) {
            if (newa[i] != newa[i-1] +1) {
                return false;
            }
        }
        return found;
    }
}

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int count = 0;
        int max = -1;
        for (int i = 0; i < arr.length;i++) {
            max = Math.max(arr[i], max);
            if (max == i) {
                count++;
            }
        }
        return count;
    }

 
}

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int add  =0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < Math.max(arr1.length, arr2.length);i++) {
            int index1 = arr1.length - 1 - i;
            int index2 = arr2.length - 1 - i;
            int num1 = index1 < 0 ? 0 : arr1[index1];
            int num2 = index2 < 0 ? 0 : arr2[index2];
            int num3 = add + num1 + num2;
            if (num3 == -1) {
                num3 = 1;
                add = 1;
            } else {
                add = -(num3  / 2);
                num3 %= 2;
            }
            res.add(num3);
        }

        if (add==-1) {
            res.add(1);
            res.add(1);
        } else if (add==1){
            res.add(add);
        }

        // 去除前导0
        while(res.size() > 1 && res.get(res.size()-1) == 0) {
            res.remove(res.size()-1);
        }
        
        int[] resArr = new int[res.size()];
        for (int i = 0; i < res.size();i++) {
            resArr[i] = res.get(res.size()-1-i);
        }
        return resArr;
    }
}