Location>code7788 >text

dynamic programming

Popularity：327 ℃/2025-01-18 16:02:07

A sentence I saw on other blogs: In the final analysis, computers can only do one thing-exhaustion; all algorithms are exhaustive methods of how to make computers "smart".

What is dynamic programming

Dynamic programming is a strategy that decomposes complex problems into small problems to solve. Different from the divide-and-conquer algorithm, the divide-and-conquer algorithm requires that each sub-problem is independent of each other, while the sub-problems of dynamic programming are interrelated.

top down

Recursion is a common top-down problem. Use Fibonacci numbers as an example: if you want the result of f(10), you need to know the result of f(9), and then by analogy until you need to know the values ​​of f(1) and f(2), and finally return step by step to get the final result.This idea of ​​finding the initial value from the result is called top-down。

 ```

int Fib(int n)
{
//Initial value f(0)=1,f(1)=1
    if(n==1||n==2)
    return 1;

    return Fib(n-1)+Fib(n-2);

}

```

bottom up

Dynamic programming is a bottom-up problem. It is also a Fibonacci number problem: the result of f(10) is still required. This time, it starts from f(1) and f(2) and evaluates upward until the result of f(10) is obtained, and finally returns the result.This idea of ​​pushing from initial conditions to results is called top-down.。

```

int Fibi(int n)
{
    std::vector<int> dp(n,0);
    int i=0;
    dp[0]=1;
    dp[1]=1;
    for(i=2;i<n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n-1];
}

```

I think these two methods are often considered at the same time, the results are obtained, and finally the specific implementation method is selected according to the actual situation.

state transition equation

The state transition equation is actually the core of solving the problem. The above dp[i]=dp[i-1]+dp[i-2] is the state transition equation.

Dynamic programming example problem

Stair climbing question:

/problems/climbing-stairs/

There are N steps. You can climb 1 or 2 steps at a time. How many ways can you climb to the top?

Problem-solving ideas: Set the staircase series reasoning to get a result similar to the Fibonacci sequence.

```

int climbStairs(int n)
{
    std::vector<int> dp(n,0);
    int i=0;
    dp[0]=1;
    dp[1]=2;
    for(i=2;i<n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n-1];
}

```

Problem optimization (rolling array)

According to the analysis of the above algorithm, it is found that there is no need to enumerate each array, only three status data need to be saved. Optimize using the idea of ​​rolling arrays:

```

int Fibi(int n)
{
    int dp;
    int i=0,
    pre1=1,
    pre2=2;
    for(i=2;i<n;i++)
    {
        dp=pre2+pre1;
        pre1=pre2;
        pre2=dp;
    }
    return dp;
}

```

The simple understanding of rolling array is to make the array roll up and use a fixed number of spaces for storage each time to achieve compression and save storage space.

 

write to the end

Finally, I would like to add that the Fibonacci sequence can actually be used directly.formulaGet results.

There are also fewer reference articles in the blog this time, and many have subjective thoughts. I hope you can point out the problem immediately. Thank you very much.

 

 

Reference article:

/2020/01/23/data-struct-learn-07-base-dp#dynamic-programming

/s?__biz=MzI2OTE0ODY5Mw==&mid=2247525996&idx=1&sn=3d76f5fc2feb0559b4c92949799975fa&chksm=ebd22c9d8f67e1092763fb3e582a7141482e85220e61e5a359775545e902954f3228873b3b53&scene=27

/qq_41655898/article/details/120174686

/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145

/overxus/p/18167834

 

<Previous Next>