Leetcode Problem Solving (Dynamic Programming)

You can see from this diagram that there’s a lot of double counting going on here, and how do we avoid that? We can create an array memo outside the program, and the memo[I] actually memorizes the ith Fibonacci sequence.

    
    #include <iostream>
    #include <ctime>
    #include <vector>using namespace std; vector<int> memo; int num = 0; Int fib(int n){num ++;if( n == 0 )
            return 0;
    
        if( n == 1 )
            return 1;
    
        if( memo[n] == -1 )
            memo[n] = fib(n-1) + fib(n-2);
    
        return memo[n];
    }
    
    int main() {
    
        num = 0;
    
        int n = 42;
        memo = vector<int>(n+1,-1);
    
        time_t startTime = clock();
        int res = fib(n);
        time_t endTime = clock();
    
        cout<<"fib("<<n<<") ="<<res<<endl;
        cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
        cout<<"run function fib() "<<num<<"times."<<endl;
    
        return 0;
    }
    
Copy the code

We use an array of memos, so it’s called mnemonic search. Mnemonic search is just adding planning to recursion, it’s a top-down problem solving, and we assume that we’ve solved the basic problem, that we know fib of n minus one and FIB of n minus two, and then we can solve for the NTH number.

If we can solve problems from the top down, we can also solve problems from the bottom up, but most of the time we are used to the former.

    #include <iostream>
    #include <ctime>
    #include <vector>
    using namespace std;
    
    // Dynamic programming
    int fib( int n ){
    
        vector<int> memo(n+1.- 1);
    
        memo[0] = 0;
        memo[1] = 1;
        for( int i = 2 ; i <= n ; i ++ )
            memo[i] = memo[i- 1] + memo[i2 -];
    
        return memo[n];
    }
    
    int main(a) {
    
        // The result will overflow
        int n = 1000;
    
        time_t startTime = clock();
        int res = fib(n);
        time_t endTime = clock();
    
        cout<<"fib("<<n<<") ="<<res<<endl;
        cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    
        return 0;
    }
    
Copy the code

The first dynamic programming problem

Leetcode 70. Take the stairs

Their thinking

Let’s think recursively about breaking up a big problem into smaller problems.

Code implementation (recursive)

#include <iostream>
    #include <vector>using namespace std; Class Solution {private: vector<int> memo; int calcWays(int n){if( n == 0 || n == 1)
                return 1;
    
            if( memo[n] == -1 )
                memo[n] = calcWays(n-1) + calcWays(n-2);
    
            return memo[n];
        }
    public:
        int climbStairs(int n) {
    
            memo = vector<int>(n+1,-1);
            returncalcWays(n); }};Copy the code

Code implementation (dynamic programming)

And we’ll see that just like Fibonacci above, it’s easy to convert to dynamic programming.

#include <iostream>
    #include <vector>using namespace std; Class Solution {public: int climbStairs(int n) {vector<int> Memo (n+1, -1); memo[0] = 1; memo[1] = 1;for ( int i = 2; i <= n; i++ ) {
                memo[i] = memo[i-1] + memo[i-2];
            }
    
            returnmemo[n]; }};Copy the code

Similar problems

• leetcode 120
• leetcode 64

Overlap subproblem found

Leetcode 343. Integer split

Their thinking

For a problem if there is no idea, we can first consider the violent solution. In other words, how do we enumerate all the partitions of the positive integer n, we don’t know how many loops there are, and we usually have to use recursion. Brute force solution: Backtrack through all the possibilities of dividing a number. O(2^n)

The recursion tree exists because it has the optimal substructure and by finding the optimal solution of the subproblem, you can get the optimal solution of the original problem.

Optimal substructure

• By finding the optimal solution of the sub-problem, the optimal solution of the original problem can be obtained

Code implementation

To achieve 1

    #include <iostream>
    #include <cassert>
    
    using namespace std;
    
    class Solution {
    private:
        int max3( int a , int b , int c ){
            returnmax( a , max(b,c) ); } // The largest product int that can be obtained by dividing n (at least two parts)breakInteger( int n ){
    
            if( n == 1 )
                return 1;
    
            int res = -1;
            for( int i = 1 ; i <= n-1 ; i ++ )
                res = max3( res , i*(n-i) , i * breakInteger(n-i) );
            return res;
        }
    public:
        int integerBreak(int n) {
            assert( n >= 1 );
            return breakInteger(n); }};Copy the code

The 2

It contains overlapping subproblems, and here is the mnemonized search version:

    
    class Solution {
    private:
        vector<int> memo;
    
        int max3( int a , int b , int c ){
            returnmax( a , max(b,c) ); } // The largest product int that can be obtained by dividing n (at least two parts)breakInteger( int n ){
    
            if( n == 1 )
                return 1;
    
            if( memo[n] ! = 1)return memo[n];
    
            int res = -1;
            for( int i = 1 ; i <= n-1 ; i ++ )
                res = max3( res , i*(n-i) , i * breakInteger(n-i) );
            memo[n] = res;
            return res;
        }
    public:
        int integerBreak(int n) {
            assert( n >= 1 );
            memo = vector<int>(n+1, -1);
            return breakInteger(n); }};Copy the code

Realize 3 dynamic programming

Now let’s solve this problem using the bottom-up approach, which is dynamic programming

    
    class Solution {
    
    private:
        int max3( int a , int b , int c ){
            return max(max(a,b),c);
        }
    public:
        int integerBreak(int n) {// The memo[I] indicates the largest product of the number I. Vector <int> Memo (n+1, -1); memo[1] = 1;for( int i = 2; i <= n; I ++) {// Evaluate memo[I]for( int j = 1; j <= i-1; j++ ) { // j + (i-j) memo[i] = max3( memo[i], j*(i-j), j*memo[i-j] ); }}returnmemo[n]; }};Copy the code

Similar problems

• leetcode 279
• leetcode 91
• leetcode 62
• leetcode 63

State definition and state transition

Leetcode 198

Definition of state

Consider stealing houses in the range [x…n-1] (function definition)

Transition of state

F (0) = Max {v (0) + f (2), v (1) + f (3), v (2) + f (4),… , v(n-3) + F (n-1), V (n-2), v(n-1)}(state transition equation)

Their thinking

The first thing is again, if you don’t have an idea, consider the violent solution first. Check all the houses, for each combination, check if there are adjacent houses, if not, record their value, find the maximum. O((2^n)*n)

Note the definition of state: Consider stealing houses in the range [x… n-1] (function definition)

According to the definition of a state, the decision of the state of the transfer: f (0) = Max {v (0) + f (2), v (1) + f (3), v (2) + f (4),… , v(n-3) + F (n-1), V (n-2), v(n-1)}(state transition equation)

In fact, our recursive function is implementing state transitions.