// Topcoder SRM 467 DIV 2, L1: ShorterSuperSum
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
ShorterSuperSum obj = new ShorterSuperSum();
System.out.println(
obj.calculate(14, 14)
);
}
}
// change to public before submit
class ShorterSuperSum {
public int calculate(int k, int n) {
return SuperSum(k, n);
}
private int SuperSum(int k, int n) {
if (k == 0)
return n;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += SuperSum(k - 1, i);
}
return sum;
}
}
is this dynamic programming?
ReplyDeletei think this is faster:
ReplyDeleteint main(){
int k, n;
cin>>k>>n;
vector< vector > d;
for(int i=0; i<=k; i++)
{
vector temp;
for(int j=0; j<=n; j++)
{
if(i==0)
temp.push_back(j);
else if (j==0)
temp.push_back(d[i-1][j]);
else
temp.push_back(temp.back() + d[i-1][j]) ;
}
d.push_back(temp);
}
cout<<d[k][n]);
return 0;
}