A few days ago, I was still hesitating. Should I focus on cultivating the ability to do projects or practicing algorithms and data structures , And then it turns out that this scene is a little familiar . Once upon a time in a month , I have three important things to solve , At the beginning of that month, I kept thinking that I should start with that , Even order the importance of these three things in your mind , There's a lot of arguing , I'm so upset , It's better to play games , Maybe we'll know how to do it later ...... It turned out that a month later , There's nothing that turns out to be very satisfying to me . The programming ability of doing projects needs to be learned , But technology is changing so fast , It is the thinking of those algorithms and the data structure designed that will never change , Since I decided to learn , Let's start with the algorithm .

A few days ago, I learned how to solve the rolling array , I've learned to plan search these days . What is memory search , It's you in the present step The decisions you make affect every decision you make next , You have to think about the outcome of the next step , Maximize the final value . Here are two examples to analyze in detail .( I think , The first step of learning algorithm is to learn examples , At the beginning, don't rush to extract those deep thoughts from the examples , Just study , When the heat is up , Naturally, we can draw inferences from one instance , Of course, the interest component is very important . Like the famous person who came here said : I read poetry , I don't mean to understand what this poem means , I just like her , I just keep reading her , Until one day , We understand each other )

1.Coins in a line : http://www.lintcode.com/en/problem/coins-in-a-line/

2.Coins in a line II : http://www.lintcode.com/en/problem/coins-in-a-line-ii/

For the first question , It's like this : Here's a row of coins , Two smart enough people pick up the coins from the beginning ( Two people have to be smart enough , Suppose Einstein and Tesla ^ ^), You can take one or two at a time , When the person who takes the last coin wins , Here you are. n A coin , Ask the first to win .

Follow the steps to solve dynamic programming

1、 state (State): When there is n A coin , How can I get it so that I can get the last coin , Let's take a step forward ,n Among the coins , I can take one or two , When you finish this step , The opponent will do the same thing ( Smart enough opponents will also consider how to get the last one ), We use Boolean types dp[x] When it's left for now x Can you win a coin when it's your turn to pick it up . At this time, we discuss it in two ways :

① I'll take one , The opponent can take one or two , So the next time it's my turn to pick up the coin , The sign of whether you can win is dp[x-2] or dp[x-3]( The opponent takes one or two ).

② I'll take two , The opponent can take one or two , Next time it's my turn to pick up the coin , The sign of whether you can win is dp[x-3] or dp[x-4].

That means , If dp[x-2] and dp[x-3] All are true( win victory ) Words , Then I am x This step must take one , So that we can make sure that in dp[x] For the time being true. Why? dp[x-2] and dp[x-3] At the same time for true Talent , Because after you take one , When it's your turn after your opponent has won, you decide whether to win dp[x-2] and dp[x-3] It's up to the opponent to decide , If one of them is false, That opponent won't let the other true happen . And vice versa , If dp[x-3] and dp[x-4] Also for true Words , Then I am x I'll take two at this step , In this way, no matter one or two opponents can prevent me from winning .

As shown in the diagram , Suppose there are four coins left , If I take one , Next, the opponent faces three , How to take can let the next step I take the last coin , But if I take two , The opponent is smart enough , It's bound to win with both , So when I face four coins, I must take one . This is equivalent to determining , If I face four coins , Then I'm sure I can win , So push up , I just need to think about whether I can construct the result of the remaining four coins .

2、 equation (Function): The state is established , The equation can then be determined . It's not hard to get out , When the rest n Coin , At this time, whether the pioneer can win or not is dp[n], Yes

dp[n] = MemorySearch(n-) && MemorySearch(n-) || MemorySearch(n-) && MemorySearch(n-);

3、 Initial state (Initialization): It's my turn to pick up the coin , If it's gone (n=0), That means the opponent has won , If there's one or two left , Then I can win , There are three left , The opponent wins , There are four left , I won . So there is

 if( == n || == n) dp[n] = false; if( == n|| == n|| == n) dp[n] =true

4、 result (Result): dp[n] ( face n A coin first )

The code implementation is as follows : Pass in n A coin as a parameter , Go back and see if you can win .

bool firstWillWin(int n) {
int dp[n+];
bool flag[n+] = {false};
return MemorySearch(dp,n,flag);
}
bool MemorySearch(int *dp,int n,bool *flag){
if(true == flag[n])
return dp[n];
flag[n] = true;
if( == n|| == n) dp[n] = false;
else if( == n||==n||==n||==n) dp[n]= true;
else{
dp[n] = ( MemorySearch(dp,n-,flag) && MemorySearch(dp,n-,flag) )|| ( MemorySearch(dp,n-,flag)&&MemorySearch(dp,n-,flag) );
}
return dp[n];
}

The above is based on the idea of ordinary memory search algorithm, simple and easy to understand , But this problem can also be solved by the method of array state shifting . After determining the initial state , Every one after f[x] All the states of can be determined by f[x-2],f[x-3],f[x-4] obtain , So there is

bool firstWillWin(int n) {
bool f[n];
if( == n ||==n|| == n|| == n) return true;
if( == n || ==n) return false;
f[] = true;
f[] = true;
f[] = false;
f[] = true;
f[] = true;
for(int i=;i<n;i++)
f[i] = (f[i-] && f[i-]) || (f[i-] && f[i-]);
return f[n-];
}

here f[x] The number of coins facing is x+1 gold . The final result is f[n-1]( namely n In the case of a coin ).

Here we are , The solution is to give you a pile of coins to take turns , Whether it will win or not . Next, let's consider a topic of expansion , Look at the second question :Coins in a line II

The meaning of the question is : Here's a bunch of coins of different values , The rules for taking coins are the same as the former , When the coin is finished, the party with high value wins , Ask the first to win .

under these circumstances , It's not like taking the last coin to win , Every step I take one or two , As long as the coin is taken out, it has the highest value . Good. , When a coin is less than or equal to 3 I'm going to start with , There's no doubt about that , Take the maximum value, the value is the highest (1 Take it when you get it 1 gold ,2 Or 3 Take it when you get it 2 gold ), Of course, when it's the opponent's turn at this time, he will take the same , But when there are four coins, how to get them . Take a chestnut , At present, it is 【1,2,4,8】 When , I'll take one , Value is 【1】, be left over 【2,4,8】, After the previous derivation , Two out of the remaining three , It was taken away {2,4}, I'll take the last one 【8】, The total value at this time is 【9】. If I take two , Value is 【3(1+2)】, be left over 【4,8】, It has to be taken away by the opponent , The total value is 【3】, Less valuable than the former , So if I have four coins left and I start at this time , I can definitely judge whether I take one or two pieces according to this method, so as to get the highest value in the end . use dp[x] To represent what's left at the moment x When you take a coin, you can get the maximum value at the end , Now I'll take one , The next round of value I face is f[x-2] or f[x-3], Because the opponent is smart enough , So he'll be based on f[x-2] and f[x-3] When he is faced with x-1 One coin or two , At this point  dp[x] = min(dp[x-],dp[x-]) + values[x] , This is the face of x The case of taking one coin out of the other . In the second case, I'll take two , The next round of value I'm facing is f[x-3] or f[x-4], Same thing , But in the end  dp[x] = min(f[x-],f[x-]) + values[x] + values[x+] , So I'll take one or two , The quantity of value is for  dp[x] = max( min(dp[x-],dp[x-])+values[x],min(dp[x-],dp[x-])+values[x]+values[x+]) , Push the same up ,dp[x] The maximum value of depends on dp[x-2],dp[x-3],dp[x-4] Value , Finally, it can be concluded that dp[n] Is to face n When you buy a coin, you can get the most value , At this point, just judge dp[n] > sum/2 To win ,sum For the total value of all coins .

The code is as follows :

bool firstWillWin(vector<int> &values) {
int sum = ;
int dp[values.size()+];
bool flag[values.size()+];
for(int i=;i<values.size()+;i++) flag[i] = false;
for(vector<int>::iterator ite = values.begin();ite!=values.end();ite++)
sum += *ite;
return sum/<MemorySearch(dp,values.size(),flag,values);
}
int MemorySearch(int* dp,int n,bool *flag,vector<int> values){
if(flag[n])
return dp[n];
flag[n] = true;
int count = values.size();
if( == n) dp[n] = ;
else if( == n) dp[n] = values[count-n];
else if( == n|| == n) dp[n] = values[count-n] + values[count-n+];
else{
dp[n] = max( min(MemorySearch(dp,n-,flag,values),MemorySearch(dp,n-,flag,values))+ values[count-n],
min(MemorySearch(dp,n-,flag,values),MemorySearch(dp,n-,flag,values))+values[count-n]+values[count-n+] );
}
return dp[n];
}

Except for this method , There is also a method similar to the second solution to the first problem , This is for the reader to realize .

The above is my personal understanding of the solution process of memory search algorithm , Every code has been tested by myself , If there is a problem , I hope you can put forward the correct idea .

Respect intellectual property , Please inform the author of the citation and indicate the source !

【 Dynamic programming 】 Memory search (C++) More articles about

  1. Memory search and dynamic programming ——DP knapsack problem

    Title Description 01 knapsack problem Yes n Weight and value are \(w_i,v_i\) The items . The total weight selected from these items shall not exceed W The items , Find the maximum value of the sum of the values in all the options . Limiting conditions 1 <= n <= 10 ...

  2. Blue Bridge Cup --- Palace of the Earth takes treasure ( Memory search = Search for +dp)

    Topic website :http://lx.lanqiao.org/problem.page?gpid=T120 Problem description X The king has a treasure house . yes n x m Matrix of lattice . One treasure per cell . Every baby is attached with value ...

  3. Dynamic programming &mdash;&mdash; Digital triangle ( recursive or Recurrence or Memory search )

    The core of dynamic programming is state and state transition equation . For this question , You need to think in an abstract way , Put the current position (i,j) As a state , Then define the indicator function of the State d(i,j) It is the maximum sum that can be obtained from the lattice ( Including the values of the lattice itself ). In this ...

  4. To enhance learning ( 3、 ... and )----- MDP The solution of dynamic programming in this paper

    Last time we talked about , The purpose of reinforcement learning is to solve Markov decision process (MDP) The best strategy for , Make it in any initial state , Can get the biggest Vπ value .( In this paper, we do not consider non Markov environment and incomplete observable Markov decision process (POMDP) Medium ...

  5. Simple dynamic programming -LeetCode198

    subject :House Robber You are a professional robber planning to rob houses along a street. Each house has ...

  6. Dynamic programming Dynamic Programming

    March 26, 2013 author :Hawstein Source :http://hawstein.com/posts/dp-novice-to-advanced.html Statement : This article uses the following protocol to authorize : ...

  7. The longest common subsequence of dynamic programming (LCS)

    from :http://segmentfault.com/blog/exploring/ LCS Problem description Definition : A sequence of S, If they are subsequences of two or more known sequences , And is the longest of all sequences that meet this condition , be ...

  8. C# Dynamic programming finds the largest substring of two strings

     // Dynamic programming finds the largest substring of two strings         public static string lcs(string word1, string word2)         {            ...

  9. C# recursive 、 Dynamic programming calculates Fibonacci sequence

    // recursive         public static long recurFib(int num)         {             if (num < 2)              ...

Random recommendation

  1. The idea of separation and inheritance realizes the preview function after uploading pictures :ImageUploadView

    This article is to introduce the realization idea of generating small picture preview directly after uploading pictures in web pages , Considering the applicability of this function , So we encapsulate the relevant logic into a ImageUploadView Components , The actual effect can be seen in the next paragraph git design sketch ...

  2. Hands teach you how to use markdown

    This is a [ Learn programming seriously ] Series of The first 3 piece article , Welcome to share . Write a message , These are the best support for me . The full text 2300 word , Reading anticipation 5 minute ] In the previous articles , I've mentioned it many times X Artifact markdown, Me too markdow ...

  3. iOS Commonly used define Macro definition

    1. Screen width, height and common size #define SCREEN_WIDTH ([UIScreen mainScreen].bounds.size.width)#define SCREEN_HEIGHT ([U ...

  4. Firefox Plug in one click switch compatible IE

    Reprint :http://mozilla.com.cn/thread-42137-1-1.html Make Firefox compatible IE Dual core extension of , Switch to IE kernel , No worries about online banking payment . Support Adblock plus and FireGes ...

  5. Enze fourth day( Loop statement One )

    hello , Hello everyone . It's time to sum up knowledge again . Today, I taught myself circular sentences in Yunhe college , Here are my general knowledge points . Let's start by adding... In the selection structure switch sentence . theory :switch Statement is a multi branch selection statement , When you need to test a lot of ...

  6. [ Reprint ] A successful Git branching model/GIT Branch management is an art

    Reprinted from :http://www.cnblogs.com/baiyw/p/3303125.html The original English text :http://www.nvie.com/posts/a-successful-git-bran ...

  7. SQL Server Locking and blocking of

    This post provides two methods , Avoidable SQL Server Abnormal or long-term blocking during transaction locking , Let users and programs wait indefinitely , Even cause connection pooling Number of connections exceeds capacity . So-called 「 Blocking 」, Is when ...

  8. CentOS 7 yum install ownCloud Build a cloud disk server

    be based on CentOS7.0 64 Bit system +ownCloud 10.0 Stable build ownCloud Is an open source free professional private cloud storage project , It can help you quickly set up a private cloud file synchronization network disk on your PC or server , can ...

  9. tornado introduction 1

    Tornado web server It's using Python It's a very lightweight . High scalability and non blocking IO Of Web Server software , The famous Friendfeed The website is built with it . Tornado With other masters ...

  10. C++ and Java Differences in class inheritance

    #include <iostream> using namespace std; class Base { public: int i; Base() { i = ; fun(); } v ...