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

- 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 ...

- 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 ...

- Dynamic programming —— 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 ...

- 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 ...

- Simple dynamic programming -LeetCode198
subject :House Robber You are a professional robber planning to rob houses along a street. Each house has ...

- 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 : ...

- 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 ...

- 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) { ...

- C# recursive 、 Dynamic programming calculates Fibonacci sequence
// recursive public static long recurFib(int num) { if (num < 2) ...

## Random recommendation

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- [ 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 ...

- 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 ...

- 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 ...

- 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 ...

- C++ and Java Differences in class inheritance
#include <iostream> using namespace std; class Base { public: int i; Base() { i = ; fun(); } v ...