Think about a DP state for every $$$i$$$.

Let $$$DP[i]$$$ be the minimum cost to reach stone $$$i$$$. What are the answer, base case and transition?

If the frog is currently at stone $$$i$$$, where could it have jumped from? According to the rules, it must have come from either stone $$$i-1$$$ or stone $$$i-2$$$. How can you use $$$DP[i-1]$$$ and $$$DP[i-2]$$$ to calculate $$$DP[i]$$$?

Instead of just checking stones $$$i-1$$$ and $$$i-2$$$, the frog can come from any of the previous $$$K$$$ stones. How can you use the previous DP states to calculate $$$DP[i]$$$?

Think about a DP state for every $$$i$$$. Does it have enough information?

If we just define $$$DP[i]$$$ as the maximum happiness on day $$$i$$$, we don't know which activity we did on day $$$i$$$, so we can't guarantee we won't repeat it on day $$$i+1$$$. What can we store to solve this? Try expanding your state with a second parameter.

Let $$$DP[i][j]$$$ be the maximum happiness on day $$$i$$$, using activity $$$j$$$ on day $$$i$$$. What are the answer, base case and transition?

If we use activity $$$j$$$ on day $$$i$$$, then on day $$$i-1$$$ we can't use activity $$$j$$$, so we have to use one of the other activities.

Think about a DP state for every $$$i$$$. Does it have enough information?

If we just define $$$DP[i]$$$ as the maximum value with items up to $$$i$$$, we don't know how much capacity we have left, so we don't know which items we are allowed to take. What can we store to solve this? Try expanding your state with a second parameter.

Let $$$DP[i][j]$$$ be the maximum value with items up to $$$i$$$, with capacity $$$j$$$. What are the answer, base case and transition?

If we are at the item $$$i$$$, we have two options: take the item or leave it. Note that we can only take the item if we have enough capacity. How can we use the previous DP states to calculate the current state?

If you try to use the exact same state from Knapsack 1, you will get MLE. Can you think on another way to write our state?

Notice that the maximum possible value is small ($$$N \le 100$$$ and $$$V_i \le 10^3$$$, so the maximum total value is $$$10^5$$$).

Let $$$DP[i][j]$$$ be the minimum capacity required to get value exactly $$$j$$$ with items up to $$$i$$$. What are the answer, base case and transition?

If we are at the item $$$i$$$, we have two options: take the item or leave it. How can we use the previous DP states to calculate the current state?

Think about comparing prefixes.

Let $$$DP[i][j]$$$ be the length of the LCS using the first $$$i$$$ characters of $$$S$$$ and the first $$$j$$$ characters of $$$T$$$. What are the answer, base case and transition?

Since this is a Directed Acyclic Graph (DAG), we can store information about a node $$$v$$$ that depends on its neighbors, without worrying about infinite loops.

Let $$$DP[v]$$$ be the longest path starting at vertex $$$v$$$. What are the answer, base case and transition?

To reach any cell $$$(i, j)$$$, you must have come from either the cell directly above it or the cell directly to its left.

Let $$$DP[i][j]$$$ be the number of ways to get to cell $$$(i, j)$$$ starting from cell $$$(1, 1)$$$. What are the answer, base case and transition?

We want to find the probability of getting more heads than tails, which means we need a specific number of heads. Try thinking about a $$$N^2$$$ approach.

Let $$$DP[i][j]$$$ be the probability of getting exactly $$$j$$$ heads using the first $$$i$$$ coins. What are the answer, base case and transition?

We can just count how many dishes have exactly 1, 2 or 3 pieces of sushi.

Define $$$dp[i][j][k]$$$ as the expected number of operations remaining when there are $$$i$$$, $$$j$$$, and $$$k$$$ dishes with 1, 2, and 3 sushi.

Manipulate the formula for $$$dp[i][j][k]$$$ to have it isolated on one side. You can now compute it recursively.

Winning and Losing states.

Calculate winning and losing states backwards, saving them in a dp.

Note that both Taro and Jiro play optimally to maximize their own score minus the other's score. This means that at each turn each player will play the move that maximizes the score.

Since players remove elements from the edges, the remaining numbers always form a contiguous subarray. Think about DP states over intervals.

Let $$$DP[i][j]$$$ be the maximum value you can get if the game is played in the interval $$$[i, j]$$$. What are the answer, base case and transition?

Let $$$DP[i][j]$$$ be the number of ways to distribute exactly $$$j$$$ candies among the first $$$i$$$ children. What are the answer, base case and transition?

Try to optimize the naive transition.

Think about prefix sums!

Since we can only combine adjacent slimes, a combined slime always represents a contiguous interval of the original array. Think about the contiguous intervals.

Let $$$DP[i][j]$$$ be the minimum cost required to combine all slimes in the interval $$$[i, j]$$$. What are the answer, base case and transition?

The constraint is $$$N \le 21$$$, think about bitmasks.

Let $$$DP[i][mask]$$$ be the number of ways to match $$$i$$$ men with the women available in $$$mask$$$. What are the answer, base case and transition?

We do not need both parameters. If our state is just the mask of available women, how do we know which men we are currently pairing?

Think about a DP state for every subtree rooted at $$$v$$$.

If we define $$$DP[v]$$$ as the number of ways to color the subtree of $$$v$$$, we run into a problem: we don't know the color of $$$v$$$, so we don't know how to color its parent. What can we store to solve this? Try expanding your state with a second parameter.

Let $$$DP[v][0]$$$ be the number of ways to color the subtree of $$$v$$$ if we color the node $$$v$$$ white and $$$DP[v][1]$$$ be the number of ways to color the subtree of $$$v$$$ if we color the node $$$v$$$ black. What are the answer, base case and transition?

Try to think of a $$$N^2$$$ solution.

Let $$$DP[x]$$$ be the maximum sum if the last flower we take has height $$$x$$$. Calculate $$$DP[x]$$$ iterating through flowers $$$i$$$ from left to right. What are the answer, base case and transition?

For each flower $$$i$$$, we can take it or not. If we take it, then we use the maximum value $$$v$$$ in $$$DP[1..h[i]]$$$ and set $$$DP[h[i]] = v + a[i]$$$. How can we optimize this transition?

Use Segment trees to optimize the transition.

The standard $$$DP[k][v]$$$ takes $$$\mathcal{O}(V^2 K)$$$. We need a faster way to compute transitions.

Think about how we count paths of length 2 using the adjacency matrix $$$A$$$.

We must build the number digit by digit.

Our state needs to track the number of digits placed and the current sum modulo $$$D$$$. We also need a boolean flag.

Instead of trying to guess the exact absolute values of the permutation, build the sequence by tracking the relative rank .

Let $$$DP[mask]$$$ be the max score to partition the rabbits in the mask. You can iterate over all submasks to form a new group.

How can you avoid redundant calculations? Try fixing one specific element (like the lowest set bit in your mask) and forcing it to be part of the new group you are creating.

Doing a standard Tree DP for every possible root takes $$$\mathcal{O}(N^2)$$$, which is too slow.

You need Rerooting DP. This technique uses two DFS passes. The first calculates the answers for subtrees going "down". The second DFS calculates the valid components strictly "above" the current subtree.

If $$$DP[i]$$$ is the max score ending with a '1' at position $$$i$$$, the naive $$$\mathcal{O}(N^2)$$$ transition looks for the best previous '1' at position $$$j$$$.

How to optimize it using Segment Tree? You will need lazy propagation.

Is there a better order to construct a tower using a specific set of blocks?

Think about Exchange Argument.

The grid is massive ($$$10^5 \times 10^5$$$), but there are very few walls ($$$N \le 3000$$$).

Try to find out a quadratic DP int the number of walls.

Manipulate the formula for transitions.

You will need Convex Hull trick.