I am participating in the Mid-Autumn Festival Creative Submission contest, please see: Mid-Autumn Festival Creative Submission Contest for details

The introduction of

Soon to the Mid-Autumn Festival, Sister Chang ‘e sent the jade Rabbit to take the moon cake collected in the world back to the Palace, but there will be layers of obstacles on the way back. Because the Jade Rabbit and sister Chang e like beauty, so there will be insufficient physical strength, at most two steps each time to stop to have a rest, but then the robbers will take advantage of the void, the jade rabbit moon cakes away part of the moon, can you help Sister Chang e keep more moon cakes?

Task description

There are a total of I steps, the Jade Rabbit needs to successfully pass this I steps to send the moon cake to chang ‘e, behind each step are hidden robbers, each robber can rob the number of moon cakes are not the same, how much is less, you need to find the moon cake that the jade rabbit loses the least through these steps.

graphic

Their thinking

If you have learned combinatorial mathematics, you may soon think of a way to help the jade rabbit. The moon cake loss is the least when you reach the I step. There are two options :(1) the moon cake loss is the least when you reach the I step. (2) Reach the i-1i-1i-1 step to lose the least moon cake, then walk two steps (the I step does not stop) can also see sister Chang ‘e. Therefore, the minimum loss of successfully sending the moon cake to Sister Chang ‘e can be expressed as minLost[I]=min(DP [I], DP [I −1])minLost[I]=min(DP [I], DP [i-1]). In order to calculate the minimum loss of reaching Sister Chang ‘e, we can first calculate the minimum loss of yutu reaching the I step and the I − 1i-1I −1 step respectively, expressed by DP [I] and DP [i-1]. And then through the min (dp [I], dp/I – 1) min (dp [I], dp] [I – 1) min (dp [I], dp [I – 1]) to find out the minimum damage to the goddess of the moon sister side.

The code description

public static int minLostDP1(int[] lost){
    int[] dp = new int[lost.length];
    // Initial state
    dp[0] = lost[0]; // take the 0th step
    // take the first step (take the first step, take the first step; Or just go to number one)
    dp[1] = Math.min(lost[1] ,lost[0]+lost[1]);
    for (int i = 2; i < lost.length; i++) {
        // State transition equation
        dp[i] = Math.min(dp[i - 2], dp[i - 1]) + lost[i];
    }
    return Math.min(dp[lost.length - 2], dp[lost.length - 1]);
}
Copy the code

Algorithm to optimize

Based on the above solution, we can further optimize. The DP array is used here to record the number of missing moon cakes in each layer. We can use two Pointers P and Q to replace the DP array in rotation.

The code description

public static int minLostDP(int[] lost){
    int tmp,p=0,q=0;
    for(int i =2; i<lost.length; i++){ tmp = q;// State transition equation
        q = Math.min(lost[i-2]+p,lost[i-1]+q);
        p = tmp;
    }
    return  q;
}
Copy the code

Task to complete

With your help, yutu has successfully completed the task, chang ‘e sister can also taste the delicious human, looking forward to the arrival of the Mid-Autumn Festival together!

The complete code

public class JueJin {
    public static void main(String[] args) {
        int[] lost = new int[] {1.2.1.2.1.2};
        int minLost = minLostDP(lost);
        System.out.println(minLost);
    }
    public static int minLostDP(int[] lost){
        int[] dp = new int[lost.length];
        // Initial state
        dp[0] = lost[0]; // take the 0th step
        // take the first step (take the first step, take the first step; Or just go to number one)
        dp[1] = Math.min(lost[1] ,lost[0]+lost[1]);
        for (int i = 2; i < lost.length; i++) {
            // State transition equation
            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + lost[i];
        }
        return Math.min(dp[lost.length - 2], dp[lost.length - 1]);
    }
    public static int minLostDP1(int[] lost){
        int tmp,p=0,q=0;
        for(int i =2; i<lost.length; i++){ tmp = q;// State transition equation
            q = Math.min(lost[i-2]+p,lost[i-1]+q);
            p = tmp;
        }
        returnq; }}Copy the code

conclusion

For solving the maximum value problem, we first think of the brute force method, although the brute force method can solve the problem, but the efficiency is very low. At this point we can think about these problems in terms of dynamic programming.

Enumeration in dynamic programming has the following characteristics:

  • There are overlapping sub-problems;
  • It must have the optimal substructure so that the optimal value of the original problem can be obtained through the optimal value of the subproblem.
  • Dp arrays are needed for optimization;
  • Only by listing the correct state transition equation can we correctly exhaust it.

Among them, overlapping subproblem, optimal substructure and state transition equation are also called the three elements of dynamic programming.

Encountered dynamic programming problems can start from these three elements, I believe that soon you can get rid of the idea of violence method.

The above is personal understanding and summary, there is wrong place to ask you to correct. Finally, I wish you a happy Mid-Autumn Festival in advance!!