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都可以达到终点.
dp
Ugly Number II
public int nthUglyNumber(int n) { int[] ugly = new int[n]; ugly[0] = 1; int m2 = 1; int m3 = 1; int m5 = 1; int f2 = 2; int f3 = 3; int f5 = 5; for(int i = 1; i < n; i++) { int min = Math.min(Math.min(f2,f3),f5); ugly[i] = min; if(min == […]
[LintCode] Longest Common Substring
public int longestCommonSubstring(String A, String B) { // write your code here int max = 0; int[][] dp = new int[A.length()+1][B.length()+1]; for(int i = 1 ; i <= A.length(); i++) { for(int j = 1 ; j <= B.length(); j++) { if(A.charAt(i-1) == B.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = 0; max = […]
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的球,放到最后, 然后其他的无所谓. (点一下,有清楚的图) public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = IOUtils.readIntArray(in,n); int max = 1002; long[][] bio = new long[max][max]; for (int […]