Daily LeetCode – day0058 0788. Rotated Digits

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 0788. Rotated Digits
class Solution {
    int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    int[][][] memo = new int[5][2][2];
    List<Integer> digits = new ArrayList<Integer>();

    public int rotatedDigits(int n) {
        while (n != 0) {
            digits.add(n % 10);
            n /= 10;
        }
        Collections.reverse(digits);
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    memo[i][j][k] = -1;
                }
            }
        }
        return dfs(0, 1, 0);
    }

    public int dfs(int pos, int bound, int diff) {
        if (pos == digits.size()) return diff;
        if (memo[pos][bound][diff] != -1) return memo[pos][bound][diff];
        int ret = 0;
        if (bound == 0) {
            for (int i = 0; i <= 9; ++i) {
                if (check[i] != -1) {
                    if (diff == 1 || check[i] == 1) {
                        ret += dfs(pos + 1, 0, 1);
                    } else {
                        ret += dfs(pos + 1, 0, 0);
                    }
                }
            }
        } else {
            for (int i = 0; i <= digits.get(pos); ++i) {
                if (check[i] != -1) {
                    if (digits.get(pos) == i) {
                        if (diff == 1 || check[i] == 1) {
                            ret += dfs(pos + 1, 1, 1);
                        } else {
                            ret += dfs(pos + 1, 1, 0);
                        }
                    } else {
                        if (diff == 1 || check[i] == 1) {
                            ret += dfs(pos + 1, 0, 1);
                        } else {
                            ret += dfs(pos + 1, 0, 0);
                        }
                    }
                }
            }
        }
        memo[pos][bound][diff] = ret;
        return ret;
    }
}

学习笔记：
这是一道困难题，用的是记忆化搜索。
memo是记忆结果的。
pos是目前进行到了第几位，
bound是是否贴近边缘的意思比如123，那现在前两位是12那就贴近边缘了，如果是11就没贴，
diff是是否出现了不一样的比如2569就会导致diff变成1。
分支也很多，写动态规划也是三维的，记忆化搜索的话也不好搞，看来答案后也思考了很久很久。
但是网上有看到状态转移总结成一条各种运算夹杂在一起的方程式，太猛了吧，不过代码可读性太低了。