• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Mar 25th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
3.
4.
5. // DCG-12
6.
7. // There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time.
8. // Given N, write a function that returns the number of unique ways you can climb the staircase.
9. // The order of the steps matters.
10.
11. // For example, if N is 4, then there are 5 unique ways:
12.
13. // 1, 1, 1, 1
14. // 2, 1, 1
15. // 1, 2, 1
16. // 1, 1, 2
17. // 2, 2
18. // What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from
19. // a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
20.
21. // input:
22. // 4
23. // 2
24. // 1 2
25.
26. // output:
27. // 5
28.
29. int waysTD(int steps, vector<int> a){
30.     if(steps == 0){
31.         return 1;
32.     }
33.     int ans = 0;
34.     for(int i=0;i<a.size();i++){
35.         if(steps-a[i] >= 0){
36.             ans += waysTD(steps-a[i],a);
37.         }
38.     }
39.     return ans;
40. }
41.
42. int waysBU(int steps, vector<int> a){
43.     vector<int> BU(steps+1);
44.     BU=1;
45.     for(int i=1;i<=steps;i++){
46.         BU[i]=0;
47.         for(int j=0;j<a.size();j++){
48.             if(i-a[j] >= 0){
49.                 BU[i] += BU[i-a[j]];
50.             }
51.         }
52.     }
53.     return BU[steps];
54. }
55.
56. int main(){
57.     freopen("ip.txt","r",stdin);
58.     int t;
59.     cin>>t;
60.     while(t--){
61.         int steps;
62.         cin>>steps;
63.         int n;
64.         cin>>n;
65.         vector<int> a(n);
66.         for(int i=0;i<n;i++){
67.             cin>>a[i];
68.         }
69.         cout<<waysTD(steps,a)<<endl;
70.         cout<<waysBU(steps,a)<<endl;
71.     }
72.     return 0;
73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top