解题思路:利用动态规划,确定出到每一个数字的时候,所对应的dp[i]为多少
dp[i]表示为在第i个数字时,前i个数字能组成的最长不下降子序列的长度
例如给出一个数列: 1 3 5 2 8 7
dp[4]=4(注意i为下标,数字8对应的下标为4,通过观察,到达数字8时,所能够构成的最长不下降子序列为 1 3 5 8,即长度为4)而我们需要用代码去实现这个过程
找出dp[i]的转移特性方程——当我们给出的序列长度为1时,那么我们的dp[i]=dp[1]=1,只有这唯一的结果,当我们输入的序列长度大于1时,初始化所有的dp[i]为1(因为我们可以将数列的每一位都当成是一个不下降子序列,长度为1,不过我们需要找出的是最长的不下降子序列)
直接上代码(语法类的问题可以去菜鸟教程搜寻)
通过两个for循环依次找到第i个数字的前j个数字组成的序列中,最长不下降的子序列为多少
第一次写题解QAQ(如有不对的地方请指正谅解
注意事项:
对于有些特定的题目,dp数组需要提前定义好长度,以防止数组越界,本题中寻找某个数字的最长上升序列时,就需要找到该数字前一项的最长上升序列
代码中的#include<algorithm>没有用上,故可以不写,在最核心的比较部分,也可以使用algorithm中的max函数进行比较。
参考代码:
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:651 |
C语言训练-求素数问题 (C语言代码)浏览:727 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:633 |
【绝对值排序】 (C语言代码)浏览:717 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:642 |
简单的for循环浏览:1410 |
【计算直线的交点数】 (C语言代码)浏览:1450 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:548 |
蚂蚁感冒 (C语言代码)浏览:1333 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:599 |