[数据结构与算法]leetcode 650. 2 Keys Keyboard | 650. 只有两个键的键盘（暴力递归-＞傻缓存-＞DP）

题目

https://leetcode.com/problems/2-keys-keyboard/description/

题解

再一次印证了我在 总结 DP 模型套路 中说的：从递归->DP之后，新的代码已经脱离原有含义了，且整个优化过程可以不看题意、仅从代码逻辑上进行改写。对于改成DP之后的代码，它是否与题意还有联系已经不重要了。能强行解释吗？可以，但是自顶向下和自底向上本来就是两个完全相反的理解方式，强行解释之后早已不是我的本意了。

喷一下官方题解：上来就贴所谓的“状态转移方程”，这玩意儿谁能看懂？明显是拿结论去推原因，给结论重新编一个看似有道理的解释，实际上已经与最原始的思维过程相差甚远了。

详见 Solution 1~4。

4次提交，一次更比一次慢，这是我没想到的。。

分析 dp 表的依赖关系草稿：

class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        // Solution 0: 不可转化成DP的暴力递归(AC)
//        process0(n, 2, 1, 2);
//        return result;

        // Solution 1: 可转化为DP的暴力递归(AC)
//        return 2 + process1(n, 2, 1);

        // Solution 2: 暴力递归+傻缓存(AC)
//        int[][] dp = new int[n + 1][n + 1]; // cur, copied
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j <= n; j++) {
//                dp[i][j] = -1;
//            }
//        }
//        return 2 + process2(n, 2, 1, dp);

        // Solution 3: DP(AC)
        int[][] dp = new int[n + 1][n + 1]; // cur, copied
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        for (int copied = n; copied >= 0; copied--) {
            for (int cur = n - 1; cur >= 0; cur--) {
                // copy all
                int p1 = Integer.MAX_VALUE;
                if (copied != cur) p1 = dp[cur][cur];
                if (p1 != Integer.MAX_VALUE) p1++;
                // paste
                int p2 = Integer.MAX_VALUE;
                if (cur + copied <= n) p2 = dp[cur + copied][copied];
                if (p2 != Integer.MAX_VALUE) p2++;

                dp[cur][copied] = Math.min(p1, p2);
            }
        }
        return 2 + dp[2][1];
    }

//    public int process2(int n, int cur, int copied, int[][] dp) {
//        if (cur > n) return Integer.MAX_VALUE;
//        if (dp[cur][copied] >= 0) return dp[cur][copied];
//
//        // copy all
//        int p1 = Integer.MAX_VALUE;
//        if (copied != cur) p1 = process2(n, cur, cur, dp);
//        if (p1 != Integer.MAX_VALUE) p1++;
//        // paste
//        int p2 = process2(n, cur + copied, copied, dp);
//        if (p2 != Integer.MAX_VALUE) p2++;
//
//        dp[cur][copied] = Math.min(p1, p2);
//        return dp[cur][copied];
//    }
//
//    public int process1(int n, int cur, int copied) {
//        if (cur == n) return 0;
//        if (cur > n) return Integer.MAX_VALUE;
//
//        // copy all
//        int p1 = Integer.MAX_VALUE;
//        if (copied != cur) p1 = process1(n, cur, cur);
//        if (p1 != Integer.MAX_VALUE) p1++;
//        // paste
//        int p2 = process1(n, cur + copied, copied);
//        if (p2 != Integer.MAX_VALUE) p2++;
//
//        return Math.min(p1, p2);
//    }
//
//    int result = Integer.MAX_VALUE;
//    public void process0(int n, int cur, int copied, int steps) {
//        if (cur == n) {
//            result = Math.min(result, steps);
//            return;
//        }
//        if (cur > n) return;
//        // copy all
//        if (copied != cur) process0(n, cur, cur, steps + 1);
//        // paste
//        process0(n, cur + copied, copied, steps + 1);
//    }
}