Problem Statement – https://dmoj.ca/problem/ccc15j5

This problem is a multi-way choice DP problem, because we can distribute the pie in a lot of way. At first we will solve a simpler version of this, that is the number of ways we can distribute pie among people without any restriction.

Let f(n, k) denote the number of ways we can distribute ‘n’ slices to ‘k’ people, therefore recurrence will be f(n, k) = ∑ f(n-i, k-1) , here ‘n-i’ checks all the possible combination and since we distributed the slice, number of people will reduce to ‘k-1’.

Since mathematicians are a bit greedy at times. So, they always get at least as many of pieces of pie as the person in front of them.

In order to solve this, we add another parameter i.e, f(n, k, m) , where ‘m’ denotes the number of slice the last person took.

Now the recurrence will be f(n, k, m) = ∑ f(n-i, k-1, i) , and this time ‘i’ loop will be from ‘m’ to ‘n/k’. This is obvious.

Finally we memoize it to reduce the time complexity.

The Implementation is rather straight-forward

#include <bits/stdc++.h>
using namespace std;
int n, k;
int dp[255][255][255];
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int n, int k, int m) {
    if(dp[n][k][m] != -1) return dp[n][k][m];
    if(k == 1 || k == n) return 1;
    if(k > n) return 0;
    else {
        int ans = 0;
        for(int i=m; i<=n/k; i++) {
                ans += f(n - i, k - 1, i);
        }
        return dp[n][k][m] = ans;
    }
}
void solve() {
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    cout << f(n, k, 1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}

Problem Statement – https://codeforces.com/problemset/problem/166/E

So we will use a DP with 2 states, that is at position D and A,B,C . Think why this optimal.

f[0][N] is the number of ways from D to D to using N steps

f[1][N] is the number of ways from A,B,C to D to using N steps

From D we can go to either A,B,C. Therefore,

f[0][N]=3∗f[1][N−1]

In order to calculate f[0][N] we need to calculate f[1][N]

From f[1][N] we could got to either at D or remaining 2 positions, Hence

f[1][N]=f[0][N−1]+2∗f[1][N−1]

So, we got to relations, i.e

f[0][N]=3∗f[1][N−1]

f[1][N]=f[0][N−1]+2∗f[1][N−1]

Base cases are

f[0][0]=1

f[1][0]=0

The Implementation is quite straight forward

#include <bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000007
#define MAX 10000010
LL F[2][MAX];
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
void solve() {
    int n; cin >> n;
    F[0][0] = 1;
    F[0][1] = 0;
    for(int i=1; i<=n; i++) {
        F[0][i] = (3 * F[1][i-1])%MOD;
        F[1][i] = (F[0][i-1] + 2*F[1][i-1])%MOD; 
    }
    cout << F[0][n]%MOD << endl;
}
int main() {
    solve();
  __fastio;
  return 0;
}