DAY 4 简单DP
训练情况简介
简单DP时间安排：6.29
- 6.29
早上：过A题
下午：过B、I、K、L、N题
晚上：补个人训练2的E题、F题
A 题
题意：
从长为n的数组取m个序列，求这m个序列的最大和
思路：
//Max[j-1]目前代表的是分成i-1组前j-1个数的最大值,a[j]单独一组组成i组
//dp[j-1]代表j-1个数分成组，第j个数a[j]放在前面i组的一组中，两种方式选取较大者
代码：
相关资料：
参考题解
B 题
题意：
求给定长度为n的数组中数字出现次数超过(n+1)/2的数字
思路：
- map做法：即入桶的思想，利用map统计数字出现的次数，当某个数字出现的个数大于(n+1)/2时即为答案
- dp做法：我们统计一个num(初始为零)，当num=0时更新ans，当输入的数与ans不同时--num,相同时++num。因为最终的答案出现的次数最多，所以它一定能留到最后
dp做法学一学
I 题
题意：
找给定序列最少的递减子序列的个数
思路：
-
贪心：导弹的高度来决定拦截系统的高度，每次更新已存在的拦截系统的高度，如果没有大于等于导弹高度的拦截系统，就再添加一个新的拦截系统。
-
DP O(\(n^2\))：题意即为求解给定序列的最长上升子序列的长度，因为在最长上升子序列里面的每个导弹都不可以被替代，而其他的导弹都存在拦截系统可以拦截
最长上升子序列的求法：我是链接
[ ]博客摘记后打勾
K 题
利用动态规划求解
对于字符串s(下标1 ~ n)和t(1 ~ m)，开一个统计数组\(c[n][m](初始为0)\)
状态转移方程，对所有的\(1\leq i \leq n , 1 \leq j \leq m\)：
\[c[i][j] = \begin{cases}
c[i-1][j-1]+1, & \text {if s[i]==t[j]} \\
max(c[i-1][j],c[i][j-1]), & \text{if s[i]!=t[j]}
\end{cases}
\]
最后的答案即为\(c[n][m]\)
[ ]博客摘记后打勾
L 题
最长上升子序列 模板题
N 题
题意：
理解题意就很简单了，就是让你(0,0)开始，每次可以走k步，上下左右，但是目的地的奶酪数必须比出发地大，知道没法走为止，问你你能搜集到的最大奶酪数
(题意好好理解下，看题意看了老半天了nnd)
思路：
记忆化搜索+dp记录