c******n
发帖数: 4965 | 1 【 以下文字转载自 SiliconValleyClub 俱乐部 】
发信人: creation (努力自由泳50m/45sec !), 信区: SiliconValleyClub
标 题: ways of increasing subsequence
发信站: BBS 未名空间站 (Thu Feb 17 03:33:25 2011, 美东)
http://www.careercup.com/question?id=7725662
I thought the recursive version is rather simple, right?
int global_seq = { 1, 4,2,4,6,8,2,5 }
int ways(int sub_seq_len ) {
return ways(global_seq.length, sub_seq_len, +infinity);
}
int ways( int n, int k, int max ) {
if ( global_seq[decide_point] <= max )
return ways(n-1, k, max ) + ways (n-1, k-1, global_seq[n]);
else
return ways(n-1, k, max);
}
DP version would be
infinity = max(global_seq);
ways[0][1----K][0---infinity] = 0;
ways[0 --- global_seq.length][0][0---infinity] = 1;
for (k = 1 to K )
for (n = 1 to global_seq.length )
for( max = 1 to infinity )
if (.......)
..... same logic as above | g***s
发帖数: 3811 | 2 calculate the time complexity for your codes.【 在 creation (努力自由泳
50m/45sec !) 的大作中提到: 】 |
|
