First look at the topic :

Introduction

Dynamic programming is a confusing name for a programming technique that dramatically reduces the runtime of algorithms: from exponential to polynomial. The basic idea is to try to avoid solving the same problem or subproblem twice. Here is a problem to demonstrate its power:

Given a sequence of as many as 10,000 integers (0 < integer < 100,000), what is the maximum decreasing subsequence? Note that the subsequence does not have to be consecutive.

On the original title , Yes 10000 It's an integer , Find the length of the longest decreasing subsequence , Where subsequences can be discontinuous . for example , Given sequence 100, 5, 99, 98, The longest decreasing subsequence is 100,99,98. As can be seen from this example , It's very likely that we need to give up some elements that are too small , To make sure the numbers are bigger , So that the numbers at the back have room to go down .

For the convenience of testing , We are going to 10000 The number of integers is temporarily replaced by another number of integers .

Here is the simplest solution given by the government , I've made a few minor changes on . The essence of this approach is to find out all the descending sequences , And then find the longest .

#include <iostream>
#include <cstdio> using namespace std;
const int maxn = ;
int n;
int sequence[maxn]; int check(int start, int nmatches, int smallest); int main() {
freopen("test.in", "r", stdin);
cin >> n;
for(int i = ; i < n; i++) {
cin >> sequence[i];
}
cout << check(, , );
return ;
} int check(int start, int nmatches, int smallest) {
cout << "Check!" << endl;
cout << start << " " << nmatches << " " << smallest << endl;
int better;
int best = nmatches;
for(int i = start; i < n; i++) {
if(sequence[i] < smallest) {
better = check(i, nmatches + , sequence[i]);
if(better > best) {
best = better;
}
}
}
return best;
}

among ,text.in My data is randomly generated by me , as follows :

 

there check Functions are recursive , The termination condition for recursion is for The cycle is over , The recursive state transition is the maximum length that can be reached after adding a new number to the decreasing sequence .

If you can't understand the algorithm , Then you can see from the running results .

The operation results are as follows :

Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!
Check!

This is to say , For decreasing subsequences , We need to test every element in the original sequence that may become the last element of the current subsequence . For example, the second part of the youngest sequence 0 Element number , Because any element can be a length of 1 Of decreasing subsequences of , So the second part of the minimal sequence 0 The element number may be 64,65,97,43,5,36,92,72,87,44 Any one of them . But let's say we've chosen the second 0 The number element is 64, So the first 1 The element number could be 43,5,36,44 Any one of .

64 65 97 43 5 36 92 72 87 44

USACO Dynamic Programming (1) More articles about

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

  2. Dynamic Programming

    We began our study of algorithmic techniques with greedy algorithms, which in some sense form the mo ...

  3. HDU 4223 Dynamic Programming?( The absolute value of the sum of the least continuous subsequences O(NlogN))

    Portal Description Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solvi ...

  4. hdu 4223 Dynamic Programming?

    Dynamic Programming? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Oth ...

  5. Introduction to algorithm learning -Dynamic Programming

    Reprinted from :http://blog.csdn.net/speedme/article/details/24231197 1. What is dynamic programming ------------------------------- ...

  6. Dynamic Programming: From novice to advanced

    author :Dumitru Source :http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg An impo ...

  7. HDU-4972 A simple dynamic programming problem

    http://acm.hdu.edu.cn/showproblem.php?pid=4972 ++ and +1 There's a difference , Don't be careless . A simple dynamic programming proble ...

  8. [ Algorithm ] Dynamic programming (Dynamic programming)

    Reprint please indicate original :http://www.cnblogs.com/StartoverX/p/4603173.html Dynamic Programming Of Programming It's not a program, it's a form ...

  9. hdu 4972 A simple dynamic programming problem( Efficient )

    pid=4972" target="_blank" style=""> Topic link :hdu 4972 A simple dynamic progra ...

Random recommendation

  1. CSS3 Realize the special effect of erasing words

    CSS: .column-title { color: #9b9b9b; text-shadow: 1px 1px #d4d4d4;}.column-title:hover { color: #5a5 ...

  2. velocity freemarker Compare

    Comparison FreeMarker for ,Velocity It's simpler . Lightweight , But its function is not FreeMarker So powerful . For most applications , Use FreeMarker Than Velocity Simpler ...

  3. Use compareDocumentPosition Compare the position of two elements in the document

    PS: Respect for the original , Please quote from http://www.cnblogs.com/Raoh/p/js_compareDocumentPosition_between_two_node.html Use comp ...

  4. iOS Use macro to write singletons

    This article only introduces ARC A single example of this case In the past, I can't recite how to write a single example , That's what I know , I also know how to write singletons through macros , But I can't remember , I'll write it down today - (void)viewDidLoad {     [super v ...

  5. ASP.NET Web Forms 4.5 New features

    author :Parry Source :http://www.cnblogs.com/parry/ One . Strongly typed data control Before a strongly typed data control appears , When we bind data controls , The front desk generally uses Eval perhaps DataBinder.Eval ...

  6. Ibatis collect select Usage details

    problem : I've been in contact with Ibatis Use , When doing one to many , It's usually filled manually , Non automatic let ibatis To fill in the data . Let's use ibatis The automatic filling function of . The key is to use collection Label under sele ...

  7. 568. Maximum Vacation Days

    Problem statement:  LeetCode wants to give one of its best employees the option to travel among N ci ...

  8. html Basis and CSS Selectors

    One .html Simple foundation What is? HTML HTML It's a language used to describe Web pages . HTML Hypertext markup language : HyperText Markup Language HTML Not a programming language , It's a sign ...

  9. ACM plan

    original text :http://027xbc.blog.163.com/blog/static/128159658201141371343475/ ACM It's mainly about algorithms , The main time is spent thinking about algorithms , It's not about programming ...

  10. log4j Two classes that come with it MDC and NDC Functions and uses

    The original text is reproduced to : https://blog.csdn.net/joeyon/article/details/52982330 To achieve acquisition IP And displayed in log We must first understand log4j Two classes that come with it MDC and NDC ...