Shulou(Shulou.com)06/03 Report--

This article introduces you how to start from the frog jump steps to understand Dynamic Programming, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Dynamic programming (Dynamic Programming), referred to as DP for short, believes that everyone has encountered this word in the process of daily work or study, and dynamic planning is also the favorite question to be asked in the interview process. Ah Fan has been asked in a few interviews, which is really miserable, but fortunately, A Fan has learned, and some simple routines are known. Let's start with a topic that many people should be familiar with.

Case 1

Q: a frog can jump up one step or two steps at a time. How many ways can the frog jump up an n-step step?

Thinking

We may not have any ideas when we see this topic at first, but we can think about it a little bit. We assume how many kinds of jumping f (n) there are when a frog jumps up an n-step, then when n = 0, f (0) = 0, if there are no steps, of course there is no jump. When there is only one step, there can be only one jump; when there are two steps, there can be two jumps, one jump and two steps at a time. If we have three steps, can we just add up one step and the sum of two steps? So we can think of f (3) = f (2) + f (1), so we can deduce f (n) = f (n-1) + f (n-2).

Coding

As you can imagine from the above analysis, then we need to implement it in code. For the records that need to be used before, we can consider using an one-dimensional array to record them, so we have the following code.

Public int dp (int n) {if (n)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.