Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- // DCG-12
- // There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time.
- // Given N, write a function that returns the number of unique ways you can climb the staircase.
- // The order of the steps matters.
- // For example, if N is 4, then there are 5 unique ways:
- // 1, 1, 1, 1
- // 2, 1, 1
- // 1, 2, 1
- // 1, 1, 2
- // 2, 2
- // What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from
- // a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
- // input:
- // 4
- // 2
- // 1 2
- // output:
- // 5
- int waysTD(int steps, vector<int> a){
- if(steps == 0){
- return 1;
- }
- int ans = 0;
- for(int i=0;i<a.size();i++){
- if(steps-a[i] >= 0){
- ans += waysTD(steps-a[i],a);
- }
- }
- return ans;
- }
- int waysBU(int steps, vector<int> a){
- vector<int> BU(steps+1);
- BU[0]=1;
- for(int i=1;i<=steps;i++){
- BU[i]=0;
- for(int j=0;j<a.size();j++){
- if(i-a[j] >= 0){
- BU[i] += BU[i-a[j]];
- }
- }
- }
- return BU[steps];
- }
- int main(){
- freopen("ip.txt","r",stdin);
- int t;
- cin>>t;
- while(t--){
- int steps;
- cin>>steps;
- int n;
- cin>>n;
- vector<int> a(n);
- for(int i=0;i<n;i++){
- cin>>a[i];
- }
- cout<<waysTD(steps,a)<<endl;
- cout<<waysBU(steps,a)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement