柳婼の blog – 第94页 – 我不管，反正我最萌～

LeetCode 650. 2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.
Note:
The n will be in the range [1, 1000].

题目大意：一开始给一个A，每次只能复制所有、或者粘贴上一次复制的内容。问要想最后变成n个A，至少得经过多少步～

分析：可以用贪心算法解决，i从2到√n，尝试是否能被n整除，如果能被整除，说明可以通过复制1次粘贴i-1次得到，则计数器ans加上i次，然后将n除以i。再次判断是否能被i整除，直至不能整除为止。然后尝试下一个i……最终n如果等于1则直接返回ans，否则要加上n表示对A复制一次粘贴n-1次～

class Solution {
public:
    int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i <= sqrt(n); i++) {
            while (n % i == 0) {
                ans += i;
                n /= i;
            }
        }
        if (n != 1) ans += n;
        return ans;
    }
};

class Solution {

public:

int minSteps(int n) {

int ans = 0;

for (int i = 2; i <= sqrt(n); i++) {

while (n % i == 0) {

ans += i;

n /= i;

}

if (n != 1) ans += n;

return ans;

}

};

LeetCode 746. Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意：爬n阶的楼梯，每层都有一个cost值（0～n-1），每次可以爬1层或者2层，求爬完全程的最小花费cost（可以从第0层开始也可以从第1层开始）

分析：dp数组，每次dp[i] = cost[i] + min(dp[i-1], dp[i-2])，最终返回dp[n-1]和dp[n-2]中较小的那个～

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[0] = cost[0], dp[1] = cost[1];
        for (int i = 2; i < n; i++)
            dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
        return min(dp[n-1], dp[n-2]);
    }
};

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

int n = cost.size();

vector<int> dp(n);

dp[0] = cost[0], dp[1] = cost[1];

for (int i = 2; i < n; i++)

dp[i] = cost[i] + min(dp[i-1], dp[i-2]);

return min(dp[n-1], dp[n-2]);

}

};

[note] 隐函数求导公式的证明dy/dx=-F’x/F’y、隐函数存在定理

隐函数求导公式：

它来源于隐函数存在定理1：设函数在点得某一邻域内具有连续偏导数，，，则方程在点得某一邻域内能唯一确定一个连续且具有连续导数的函数，它满足条件，并有。

证明过程如下：将代入，得恒等式，在这个恒等式两边对求导，得，由于连续且，所以存在的一个邻域，在这个邻域内，于是得

[note] 证明：limx的x次方在x趋向于0+的时候等于1，即lim(x->0+)x^x=1

证明：

对x的x次方取对数可得：

为无穷比无穷型，用洛必达法则可得：

所以

在Windows上安装Python

在 https://www.python.org/downloads/ 上下载Python的安装包
打开安装包进行安装，确保安装了 pip 并且 Python 添加到了你的 PATH
开始菜单 -> 所有程序 -> Python -> IDLE编辑和运行Python代码～

Mac OSX上安装Python的方法

使用Homebrew安装python

如果没有安装Homebrew，先安装Homebrew /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)”
安装完Homebrew之后，通过 brew help 检验是否安装完成
输入 brew install python 安装Python 2；或 brew install python3 安装Python 3
python 或者 python3 进入Python Shell。使用 control + D 退出shell

使用程序包安装

在 https://www.python.org/downloads/ 下载安装包
Finder -> Applications -> python -> IDLE.app中编辑和运行Python代码