leetcode_650. 2 Keys Keyboard_dp

佚名 6年前 (2019-04-12) 随笔 1567人围观抢沙发百度已收录

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

初始一个A，两种操作，复制当前所有A，粘贴，问得到n个A最少需要多少步操作。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

class Solution
{
public:
    int minSteps(int n)
    {
        vector<int> dp(n+1,10000);
        dp[1] = 0;
        for(int i=1;i<=n;i++)
            for(int j=2;j*i<=n;j++)
                dp[i*j] = min(dp[i]+j,dp[i*j]);
        return dp[n];
    }
};