Dynamic programming

The world is still so small ah, and met our dearest friend ———— dynamic planning, how to say also saw two or three times, recall our old friend?

Let me take you through our dynamic tetralogy!

Dynamic tetralogy

1. Make suredpIs the state of: defined as one dimensional two dimensional or three dimensional? What does it mean?

2. Determine the state transition equation

3. Initialization, i.edpThe value of an element that can be retrieved from an array

4. Calculate from the bottom updpAnd get the optimal value (traversal order)

Poke the balloon

The title

There are n balloons, numbered from 0 to n-1, and each balloon is marked with a number, which is stored in the array NUMs.

Now you’re required to pop all the balloons. Pop the I th balloon and you get nums[I-1] * NUMs [I] * NUMs [I + 1] coins. I minus 1 and I plus 1 are the numbers of the two balloons next to I. If I – 1 or I + 1 goes beyond the bounds of the array, consider it a balloon with a number of 1.

Find the maximum number of coins you can get.

Here is an example

The sample1: Input: nums = [3.1.5.8] output:167Nums = [3.1.5.8] --> [3.5.8] --> [3.8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
Copy the code

Thinking analytical

So let’s take a look at this example based on our dynamic tetralogy

Make sure thedpArray state

Here, we are required by the problem of the solution is to pop the balloon can get the maximum amount of COINS, so this problem of sub-problem is punctured the nums in an array from I to j balloon COINS of the largest number, so we define dp array for two-dimensional arrays, and the meaning of dp [I] [j] for I to j the interval gained by the largest number of COINS.

Determine the state transition equation

So where does this maximum number of coins come from?

We see in the example that the number represented by the punctured balloon is multiplied by the number to the left and right of the balloon, We assume that the subscript of the numS array is I ‘ ‘k’ ‘j, and the index of the balloon is K, then the calculation expression of the coin obtained by the puncture of K can be expressed as nums[I] * nums[k] * nums[j]. That’s just three balloons. What if there were more balloons on the left and right?

Similarly, if a balloon with index k is punctured in the interval [I, j], we can deduce that the value of dp[I][j] is dp[I][k] obtained by puncturing all balloons to the left of K plus dp[k][j] obtained by puncturing all balloons to the right of K, Nums [I] * NUMS [k] * NUMs [j], Then the corresponding equation of state for the dp [I] [j] = Max (dp [j], [I] (dp [I] [k] + dp [k] [j] + nums nums [I] * * nums [k] [j]));

Initialization, that isdpThe value of an element that can be retrieved from an array

So when we initialize the dp array, the only value we can get is 0, so it doesn’t really matter whether we get it or not.

4. Calculate from the bottom updpAnd get the optimal value (traversal order)

It is obvious that the recursion is in reverse order. Assuming that dp[2][6] is solved first, the corresponding “DP [4][6]” needs to be solved first. If the sequential array loop is adopted, solving DP [4][6] will be carried out before solving DP [2][6], which is obviously not logical. So it’s easier to do this in reverse order

code

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size(a); vector<vector<int>> dp(n + 2, vector<int>(n + 2.0));
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = max( dp[i][j], (dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])); }}}return dp[0][n + 1]; }};Copy the code

Code parsing

We first need to expand the array, plus one on both sides, because in the title means that if the right or the left without a balloon with a substitute, so here we started from the subscript for n – 1 reverse recursion, and we are on the right element j start with interval at least one position I subscript traversal, intermediate element k is to be pricked the balloon, That is, the elements between I and J, and solve by using the state transition equation, and finally get dp[0][n + 1] is our final result

conclusion

There are still many kinds of dynamic programming topics, and the types of questions are also impossible to guard against, so we still need to learn more.

I am xiaobai, we together in the learning code on the road, repeatedly defeated, repeatedly defeated repeatedly battle!