比较轻松的一节课
- 字符串处理。不需要用到算法，只是考察对于字符串处理的API是否熟悉。
- 递归。 经典的问题，把每一个问题划归成若干相同的子问题。
- 背包问题。典型的dp问题，经常考的模型。
杂谈：计算机考研专业课的内容怎么样？很多八股文，很多都是用不到的。不能把知识转化成产品。
题目一
首字母大写
题目大意 ：读入一堆字符串，将单词首字母大写。
问题分析 ：
- 很明显的一个问题就是如何读入带空格字符串呢。getline(cin,s)
- 第二个问题，如何判断单词。
- 第三个问题，那么该怎么变成大写呢？使用 toupper 函数。
把这三个问题解决了，是不是答案就很明显了。
题目二
日志排序
题目大意：输入字符串，代表日志信息，按照一定的规则解析字符串并且排序。
问题分析：
- 主要问题是什么？主要是分析字符串，进行排序。
- 遇到什么问题？ 该如何拆解字符串呢？
题目三
字符串转化整数
题目大意：输入字符串。输出的字符串的第一个整数
问题分析：
- 该如何判断数字呢？ isdigit()。
- 该如何判断是否在范围里面呢？ 使用头文件#include <limits.h> INT_MAX 表示最大int整数。
题目四
重复者
题目大意：给定一个模板，根据输入，扩写后面的图形
问题分析：使用递归，分解成子问题。
-
使用getline 有什么需要注意的吗？记得将上面一行的回车使用 getchar消掉。
-
背包问题
问题五
01背包问题
- 上机题目是不是很快乐？现在开始讲解背包问题了。
- 上机题一般如何考察呢？一般都是考察经典的模型。然后考察你对这个模型的理解，对这个模型的转化。
- 这个题目怎么做呢？是不是可以用到闫氏dp分析呢？进行划分集合，设置状态。
- dp要怎么考虑呢？ 首先是状态表示 f(i, j)， 然后是状态计算。
- 那个怎么状态标识呢？ 一般来说都是通过经验定义的，很难自己凭空想象。
- 那么状态表示该从哪几个方面来看呢？ 首先看状态表示的集合，然后看状态表示的属性。
- 这里面集合表示什么？ 集合表示所有的选择方法。
- 这里面集合表示什么呢？ 所有从前i个物品中选择，且体积不超过j的选法方案数。
- 这里面属性表达什么 ？ 所有的选法中最大的价值。
- 怎么进行状态的计算呢？ 这个一般对应集合的划分。 划分的时候，找不同点。
- 那么如何找不同点呢？ 一般是最后一个。所以一起来看一看第i个物品的选法。
- 第i个物品，选或者不选，是不是可以分成两类呢？
所以说是不是明白了如何求 f(i, j) 最大值？ ans = max (取第i个物品， 不取第i 个物品)
如果要求数量怎么办 ？ 那么就是 ans = 取第i个物品 + 不取第i 个物品
经过分析之后，是不是怎么做很明显了。
但是到这里结束了吗？没有，一般来说，背包问题还涉及到空间优化。
怎么优化空间呢？ 把不优化的代码写出来，然后做等价变形就可以了。
问题六
点菜问题
题目分析：是不是在考察背包问题的运用呢？
算法考试的本质是什么？考察模型转化的问题。
问题七
背包问题
题目分析：该如何转化成背包问题
/*
状态定义：f[i][j] 表示前i个物品总重量恰好等于j的方案数
集合划分：根据第i个物品，选或不选将集合化成两部分
状态计算：f[i][j] = f[i-1][j] + f[i-1][j-w[i]]
*/
三步走
问题八
整数拆分
思路：做算法题很典型的想法，把问题转化成已知问题。这个就是转化成背包问题。
需要考虑组合问题。
完全背包的状态转移方程，求方案数
复习反序输出 AcWing 3379
怎么使用 reverse 函数呢？ reverse(s.begin(), s.end());