Topic:

A frog can jump up one step or two steps at a time. Ask the frog to jump on onenHow many ways are there to jump the steps?

Answer key:

Dynamic programming

class Solution { public int numWays(int n) { if(n == 0) return 1; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i < n + 1; i++){ dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007; } return dp[n]; } //by: edelweisskokoCopy the code

Resolution:

The frog jumps to the NTH step dp[n] = DP [n-1] *1+ DP [n-2] *1, which is the state transition equation in dynamic programming.

Status definition: DP [n] DP [n] indicates the jump method of n steps

State transition equation: DP [n] = DP [n-1] + DP [n-2]

Initial state: dp[0] = 1, dp[1] = 1

Return value: dp[] the last number in the array

It’s kind of like the coin formation problem, so dp has to take into account all the situations before DP, like dp is one coin away from dp and two coins away from DP or even five coins away from DP, so it’s one jump away from DP and two jump away from DP