🧩 AtCoder DP Contest Solutions

This repository contains my solutions for the problems in the AtCoder Educational DP Contest (a set of classic dynamic programming problems).

The primary goals of this project are:

To provide correct and well-structured solutions to the problems in the AtCoder Educational DP Contest.
To serve as a personal reference for fundamental dynamic programming techniques.
To offer a resource for others learning and practicing Dynamic Programming (DP).

All solutions are primarily written in C++.

Problem List and Status

Below is a quick reference table for all the problems included in the contest.

Problem ID	Problem Title	Solution Status	Key DP Technique
A	Frog 1	✅ Solved	Basic 1D DP
B	Frog 2	✅ Solved	1D DP with state transition
C	Vacation	✅ Solved	2D/3D DP (Max of three choices)
D	Knapsack 1	✅ Solved	Bounded Knapsack (0/1 Knapsack)
E	Knapsack 2	✅ Solved	Knapsack (Optimized by Value)
F	LCS	✅ Solved	Longest Common Subsequence
G	Longest Path	✅ Solved	DP on DAG (Directed Acyclic Graph)
H	Grid 1	✅ Solved	Grid DP
I	Coins	✅ Solved	Probability DP
J	Sushi	❌ To Do	Expected Value DP
K	Stones	✅ Solved	Game DP
L	Deque	✅ Solved	Game DP (Range/Interval DP)
M	Candies	✅ Solved	DP with Prefix Sum Optimization
N	Slimes	✅ Solved	Interval DP
O	Matching	✅ Solved	DP with Bitmasking
P	Independent Set	✅ Solved	Tree DP
Q	Flowers	✅ Solved	DP with Segment Tree
R	Walk	✅ Solved	DP with Matrix Exponentiation
S	Digit Sum	✅ Solved	Digit DP
T	Permutation	✅ Solved	Combinatorial DP
U	Grouping	✅ Solved	DP with Bitmasking
V	Subtree	❌ To Do	Tree DP
W	Intervals	❌ To Do	DP with Segment Tree
X	Tower	❌ To Do	Standard DP
Y	Grid 2	❌ To Do	Combinatorics/Grid DP
Z	Frog 3	❌ To Do	DP with Convex Hull Trick (CHT)

This is a personal learning repository, but suggestions for improvements in clarity or efficiency are welcome via issue reports.