解题思路
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;
}
}