650. 只有两个键的键盘 Krains 2020-08-02 09:39:39 动态规划DFS

class Solution {
    int INF = (int)1e9;

    public int minSteps(int n) {
        return helper(n, 1, 0, new Integer[n+1][n+1]);
    }

    // n是所需字符，cur是当前字符数，last是上一次复制的字符数，memo是记忆数组
    public int helper(int n, int cur, int last, Integer[][] memo){
        // 如果当前字符cur超过了n，此状态不合法，返回INF，
        // 我们会对操作次数取min，因此不会选取到INF这个状态
        if(n < cur)
            return INF;
        else if(n == cur)
            return 0;
        if(memo[cur][last] != null)
            return memo[cur][last];

        int count = INF;
        // 第一次递归代表Copy All，当cur==last时，表示已经复制过了，无需再复制
        if(cur != last)
            count = Math.min(count, helper(n, cur, cur, memo) + 1);
        // 第二次递归代表Paste，只有当上次复制有字符时Paste才有意义，否者只会徒增步数
        if(last != 0)
            count = Math.min(count, helper(n, cur+last, last, memo) + 1);

        return memo[cur][last] = count;
    }
}