3月24日

1.分解质因数

num = x1^k1 + x2^k2...

void divide(int n){
	//从2开始找质数
    for(int i = 2;i <= n / i; ++ i){
    	//i是n的一个因数就计算到最小的因数
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }
            //输出结果
            printf("%d %d\n",i,s);
        }
    }
    //如果n还是大于1，那么这个数本身就是质数
    if(n > 1) printf("%d %d\n",n,1);
    puts("");
}

2.硬币找零

    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        //dp[j]:凑足总额为j所需要钱币的最少个数为dp[j]
        //dp[i]:来源coins[i]
        vector<int> dp(amount + 1,INT_MAX);
        dp[0] = 0;
        for(int i = 0;i < n;++i){   //遍历物品
            for(int j = coins[i];j <= amount;++j)   //遍历背包
                if(dp[j - coins[i]] != INT_MAX)
                    dp[j] = min(dp[j - coins[i]] + 1,dp[j]);
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }

3.最长公共子序列

相等就左上+1 不相等就max(左，上)