目录

lc650.只有两个键的键盘

Shen 收录于每日一题

2021-09-19 约 244 字预计阅读 1 分钟

目录

650.只有两个键的键盘

动态规划

$O(n^2)$
考虑状态$f[i]$为输出恰好为$i$个$A$时的最少操作此时
${i % j == 0}, f[i] = min{(f[i], f[j] + i / j)}$，对$j$复制一次，粘贴$i/j$次

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int minSteps(int n) {
        vector<int> f(n + 1, 0);

        for(int i = 2; i <= n; i++){
            f[i] = INT_MAX;
            for(int j = 1; j < i; j++){
                if(i % j == 0){
                    f[i] = min(f[i], f[j] + i / j);
                }
            }
        }

        return f[n];
    }
};

动态规划优化

$O(n\sqrt{n})$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int minSteps(int n) {
        vector<int> f(n + 1, 0);

        for(int i = 2; i <= n; i++){
            f[i] = INT_MAX;
            for(int j = 1; j * j <= i; j++){
                if(i % j == 0){
                    int a = j, b = i / j;
                    f[i] = min(f[i], f[a] + b);
                    f[i] = min(f[i], f[b] + a);
                }
            }
        }

        return f[n];
    }
};