Dynamic programming , Matches game and winning strategies

The question is: There are 219 matches on a table and 2 players , each player can take 1,3 or 4 matches off the table , winner is who takes the last match. is there a winning strategy that guarantees for the second player to always win? .

I can't think of a way to calculate without having to do the recursion myself , now maybe 219 matches isn't that bad but if it was 1000 matches that wouldn't be so efficient.

I'd appreciate the help

When the number of matches is of the form 7$$k$$ or 7$$k$$ + 2, the second player wins; otherwise, the first player wins. I cannot claim to have an intuition of why this should be so, but once you write the program and notice the pattern, it is easy to prove by induction.

#include <stdio.h>

#define MAX_N 100

bool w[MAX_N]; /* true = player 1 wins; false = player 2 wins */

int main() {
w[1] = true;
w[2] = false;
w[3] = true;
w[4] = true;

for (int i = 5; i < MAX_N; i++) {
w[i] = !w[i - 1] || !w[i - 3] || !w[i - 4];
if (!w[i]) {
printf("Player 2 wins for n=%d\n", i);
}
}
}


The program basically hard-codes the trivial cases, then says "Player 1 wins if and only if there exists a move that takes the game into a state where Player 2 wins". Output:

Player 2 wins for n=7
Player 2 wins for n=9
Player 2 wins for n=14
Player 2 wins for n=16
Player 2 wins for n=21
Player 2 wins for n=23
Player 2 wins for n=28
Player 2 wins for n=30
...