题目

思路

因为每次只有两个操作：复制或粘贴。可以用深搜把所有情况遍历。
采用一个memo数组记忆化搜索

class Solution {
public:
    int INM = INT_MAX - 10;
    int memo[1001][1001];

    int minSteps(int n) {
        if (n == 0) return 0;
       return dfs(n, 1, 0);
    }

    int dfs(int n, int i, int j) {
        if (i > n) return INM;
        if (i == n) return 0;
        if (memo[i][j] != 0) return memo[i][j];
        int m = INM;
        if (j > 0) m = min(m, dfs(n, i + j, j));
        if (i != j) m = min(m, dfs(n, i, i));
        memo[i][j] = m + 1;
        return m + 1;
    }
};