动态规划算法通常用于求解具有某种最优性质的问题。 那它和贪心有区别吗？ 当然有。不然叫动态规划干啥？ 幼儿园英语老师：DP是啥？ 小盆友：Dog&Peppa pig 英语老斯：恩恩！真聪明！ 然而，你是小盆友吗？ 如果是 如果不是， DP是D****** P*******的缩写。 意思是动态规划。 聪明的bolt告诉你：是Dynamic Programming的缩写！！！ 动态规划注重 表示状态，转移状态 so 讲一个栗子： LIS： 最长上升子序列 这是线性动态规划中最经典的栗子之一。 最长上升子序列（Longest Increasing Subsequence，LIS），指一个序列中最长的单调递增的子序列。 注意不是子串，所以可以不相邻。 比如说： 序列：3 2 1 4 6 8 7 9 它的LIS是5 3 4 6 8 9 或3 4 6 7 9 或2 4 6 8 9 ······ 还有很多种情况。 于是我们珂以得出： 动态规划的最优解，有不同的组合情况，但答案只有一个。 所以，如果NOIP出了动态规划的题目时，一般会叫你求值，而不是求情况。 这是好处！ BUT，有的老师不会好心，会给更多限制条件，使Ans只有一种情况，那就更有难度了。 LIS问题要用动态规划做。 方法一： 这是一个好理解的方法。 但是更好使耗时 不难看出，dp [ i ]就是第 i 个数的LIS 那代码怎么实现的呢？ 先别急，我们在举个生活中的栗子。 老师要你算1+2+3+4+5+6+7+8+9=？时，你会算得45， 老师再问你1+2+3+4+5+6+7+8+9+10=？时，你是会用1+···+10，还是用之前算的45+10？ 聪明人会用后面一种。 所以，我们根据这个方便的原理，发现我每次计算dp [ i ] 时，如果用到了前面的 dp 值，则会减少一定的计算量。 在我们每次枚举一个数的dp值时，只要扫描在它前面比它小的数，那些比他小的数的dp值的最大值+1就是所求数的dp值 因为比所求数小的数的dp值表示它的LIS，再来一个比它大的数，大树数的LIS就等于小数的LIS+1. 但由于小数的LIS有大有小，我们又要求最长子序列，我们就要取最大值。 一番思考后，我们找到了状态转移方程，也就是动态规划中最重要的东西： 对于每一个 i ，我们枚举它前面的数 j，if (i > 它前面的数 j ) dp [ i ] = max ( dp [ i ] , dp [ j ] + 1 ) ; 这个算法的时间复杂度是O(n^2)的，慎用。 code: 复制代码 1 int n,a[1001]/*用来存序列*/,dp[1001]/*dp值*/;//数组大小根据题目而定。 2 cin>>n; 3 dp[1]=1; //1的dp值为1 4 for(int i=1;i<=n;i++) 5 cin>>a[i]; 6 for(int i=1;i<=n;i++) 7 { 8 for(int j=1;ja[j]) 11 { 12 dp[i]=max(dp[i],dp[j]+1); //状态转移 13 } 14 } 15 } 16 cout<=a[x]){ 11 r=m; 12 } 13 else{ 14 l=m+1; 15 } 16 } 17 return l; 18 }//二分查找 19 int main(){ 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 22 dp[1]=a[1]; 23 for(int i=2;i<=n;i++){ 24 if(a[i]>dp[ans]){ 25 dp[++ans]=a[i]; 26 } 27 else{ 28 int pos=find(i); 29 dp[pos]=a[i]; 30 } 31 } 32 printf("%d",ans); 33 return 0; 34 } 复制代码 这就是LIS问题，希望大家好好理解这个问题，因为他真的狠重要！ 今天的分享就到这里，我们下次见。https://www.cnblogs.com/sillyben/p/9915268.html