#include <iostream>
using namespace std;

bool isSubsetSum(int set[], int n, int sum) {
    // The value of subset[i][j] will be true if
    // there is a subset of set[0..j-1] with sum
    // equal to i
    bool subset[n + 1][sum + 1];
 
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
        subset[i][0] = true;
 
    // If sum is not 0 and set is empty,
    // then answer is false
    for (int i = 1; i <= sum; i++)
        subset[0][i] = false;
 
    // Fill the subset table in bottom up manner
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j]
                               || subset[i - 1][j - set[i - 1]];
        }
    }

     for (int i = 0; i <= n; i++) {
       for (int j = 0; j <= sum; j++)
          printf ("%4d", subset[i][j]);
       printf("\n");
     }
 
    return subset[n][sum];
}

int main() {
    int set[] = { 3, 34, 4, 12, 5, 2 };
    int sum = 9;
    int n = sizeof(set) / sizeof(set[0]);
    if (isSubsetSum(set, n, sum) == true)
        printf("Found a subset with given sum");
    else
        printf("No subset with given sum");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int countFriendsPairings(int n) {
    int dp[n + 1];
    
    for (int i = 0; i <= n; i++) {
        if (i <= 2)
            dp[i] = i;
        else
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
 
    return dp[n];
}

int main() {
    int n = 7;
    cout << countFriendsPairings(n) << endl;
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
int count( int S[], int m, int n ) {
    int i, j, x, y;
    int table[n + 1][m];

    for (i = 0; i < m; i++)
        table[0][i] = 1;
        
    for (i = 1; i < n + 1; i++) {
        for (j = 0; j < m; j++) {
            x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0;
            y = (j >= 1) ? table[i][j - 1] : 0;

            table[i][j] = x + y;
        }
    }
    return table[n][m - 1];
}

int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    cout << count(arr, m, n);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
int getMaxGold(int gold[][MAX], int m, int n) {
    int goldTable[m][n];
    memset(goldTable, 0, sizeof(goldTable));
 
    for (int col=n-1; col>=0; col--) {
        for (int row=0; row<m; row++) {
            int right = (col==n-1)? 0: goldTable[row][col+1];
            int right_up = (row==0 || col==n-1)? 0: goldTable[row-1][col+1];
            int right_down = (row==m-1 || col==n-1)? 0: goldTable[row+1][col+1];
            goldTable[row][col] = gold[row][col] + max(right, max(right_up, right_down));                                      
        }
    }
    
    int res = goldTable[0][0];
    for (int i=1; i<m; i++)
        res = max(res, goldTable[i][0]);
    return res;
}

int main() {
    int gold[MAX][MAX]= { 
        {1, 3, 1, 5},
        {2, 2, 4, 1},
        {5, 0, 2, 3},
        {0, 6, 1, 2}
    };
    int m = 4, n = 4;
    cout << getMaxGold(gold, m, n);
    return 0;
}

#include <iostream>
using namespace std;
 
int getNoOfWays(int n){
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    return getNoOfWays(n - 1) + getNoOfWays(n - 2);
}

int main() { 
    int n;
    cin >> n;
    cout << getNoOfWays(n) << endl;
    return 0;
}