Dynamic programming algorithm in C++ and its application skills

Dynamic Programming (DP) is an efficient algorithm used to solve some problems with overlapping sub-problems and optimal sub-structure properties. There are some techniques to improve efficiency when implementing dynamic programming algorithms in C language. This article will introduce the dynamic programming algorithm in C and its application techniques.

The main idea of ​​the dynamic programming algorithm is to decompose the problem into a series of sub-problems, and when solving each sub-problem, retain a state and use this state to avoid repeated calculations. The dynamic programming algorithm can solve some computationally expensive problems because it only needs to calculate each subproblem once instead of every time.

1. Three elements of dynamic programming

The dynamic programming algorithm needs to meet three elements:

(1) Optimal substructure: the optimal substructure of the problem The optimal solution contains the optimal solutions to its subproblems.

(2) No aftereffect: All states in the process are only related to the current state and have nothing to do with the previous state.

(3) Overlapping sub-problems: Multiple sub-problems overlap each other, which can avoid repeated calculations.

2. Basic classification of dynamic programming

There are two basic classifications of dynamic programming: one is state-based dynamic programming, and the other is decision-based dynamic programming. State-based dynamic programming refers to saving the solutions to each sub-problem during calculation, and then calculating the solution to the larger problem based on the values ​​of these solutions. The state is usually saved using a data structure, such as an array. Decision-based dynamic programming refers to determining the optimal solution to the larger problem based on the optimal solution of each sub-problem during calculation. This method is often used to solve optimization problems or when calculating the minimum value.

3. Application skills of dynamic programming

When implementing the dynamic programming algorithm in C, there are some application skills that can improve efficiency. These techniques include:

(1) Use constants instead of array subscripts: In some dynamic programming problems, multiple accesses to the array are required. At this time, you can replace the subscript of the array with a constant, which can speed up access. For example:

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

You can use variable k to replace the subscript of the dp array:

for(int k=2;k<=n+m;k++){
    for(int i=1;i<=n;i++){
        int j = k-i;
        if(j<1 || j>m) continue;
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

(2) Optimize the array: In some dynamic programming problems, the size of the array is very large, which may cause memory limitations . At this time, you can use a rolling array or the first dimension of a two-dimensional array to save the intermediate results. For example:

int dp[N][M];
for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

can be optimized to:

int dp[2][M];
for(int i=0;i<N;i++){
    int cur = i%2, pre = (i+1)%2;
    for(int j=0;j<M;j++){
        dp[cur][j] = max(dp[pre][j],dp[cur][j-1])+1;
    }
}

(3) Saving space: In some dynamic programming problems, only the most recent states need to be saved instead of the entire array. At this point, you can use a scrolling array to save only the most recent states.

(4) Avoid repeated calculations: In some dynamic programming problems, there may be repeated sub-problems. At this time, you can use memorized search or bottom-up dynamic programming to avoid repeated calculations.

4. Examples of dynamic programming

The following are some examples of dynamic programming problems:

(1) Fibonacci Sequence: Fibonacci A sequence means that starting from 0 and 1, each number is equal to the sum of the previous two numbers. For example, 0, 1, 1, 2, 3, 5, 8, 13, 21.

The recursion formula is: f[n] = f[n-1] f[n-2]

Using dynamic programming algorithm, the following can be achieved:

int dp[N];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
    dp[i] = dp[i-1] + dp[i-2];
}

(2) Knapsack problem: The knapsack problem means that there are N items, each item has a weight and a value. Given the capacity C of a knapsack, find the maximum value that can be loaded without exceeding the capacity of the knapsack.

Using dynamic programming algorithm, you can achieve the following:

int dp[N][C];
for(int i=0;i<N;i++){
    for(int j=0;j<C;j++){
        dp[i][j] = 0;
    }
}
for(int i=0;i<N;i++){
    for(int j=0;j<=C;j++){
        if(j>=w[i]){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
        else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

The above is a brief introduction to dynamic programming algorithm and its application skills in C. For complex dynamic programming problems, time complexity and space complexity also need to be considered. Therefore, when implementing a dynamic programming algorithm, it is necessary to consider various factors and choose an appropriate method.

The above is the detailed content of Dynamic programming algorithm in C++ and its application skills. For more information, please follow other related articles on the PHP Chinese website!