Menu Sidebar
Menu

dp

Min Cost Climbing Stairs

一道基础的dp题, dp[i]的意义是表示在ith位置上, 最小的cost. 那么 dp[i] = Math.min(dp[i-2], dp[i-1]) + cost[i] 表示选择前一步或者前两步中最小的cost, 然后走当前这一步. 最后的答案是选择Math.min(dp[cost.length – 1], dp[cost.length – 2]), 因为从cost.length -1和cost.length-2都可以达到终点.

Ugly Number II

因为定义的ugly number是2,3,5的倍数, 所以新的ugly number也是由他们的倍数组成. 每次找到三个数中最小的, 然后求它的倍数.

[LintCode] Longest Common Substring

Codeforces Round #309 (Div. 1) A. Kyoya and Colored Balls

原题:http://codeforces.com/contest/553/problem/A 题目大意: k个颜色, n个球, 球之间没区别. 问怎么放能至少让一个i个颜色的球排在i+1的颜色的球的前边. 分析:这题目看起来是很拗口, 我看着发愣了一会儿才明白. 颜色是有顺序的.第i+1颜色的前边至少要有一个i颜色的球, 这个i不是固定的. 1<=i<=k-1, 所以题目也可以解释成,至少一组球是有序的, 这个有序不一定是连续的球. 因为i表示的颜色是个范围, 所以要用dp来做, 假设i = 1, 这时候就一种颜色, 因为球和球之间无区别, 所以答案是1. i = 2的时候, 因为要保持以上的条件, 所以我们选一个颜色为2的球,放到最后, 然后其他的无所谓. (点一下,有清楚的图)

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.