表格法

习题预习

1. 根据不同年龄层的财务目标，将支出分类，以便更好地了解该年龄层的花费习惯。
2. 分析哪些餐厅在不同的城市或地区经常被顾客点餐，以协助制定营销策略。
3. 纪录每位员工的出席率，早退率和迟到率，以协助管理人员确定员工出勤表现并提供相应的奖励或惩罚。
4. 记录一个公司的优惠券使用量，以解决促销营销策略的投入和回报。
5. 通过记录每位学生的出勤率、作业完成情况和考试成绩来衡量教育系统的效果，以判断学生的整体表现和制定针对性的教育改革计划。

说明知识

Tabulation（表格法）是一种动态程式设计方法，用于解决子问题互相不相交的问题。通常用于解决最短路径、最长公共子序列、编辑距离等问题。

在Tabulation方法中，动态规划的解决方案从最小的子问题开始，通过填充表格来解决更大的问题。表格的每个单元格代表问题的某个特定状态，每个单元格的计算取决于其他单元格中已经计算的值（即子问题）。

举例来说，考虑最短路径问题。一个图形可以用一个邻接矩阵来表示，其中矩阵的每个元素代表一对节点之间的边。如果两个节点之间没有边，那么该元素为无穷大。

步骤如下：

1. 创建一个二维表格来记录每个节点的最短路径。
2. 初始状态下，表格中每个元素都是无穷大，除了起始节点的元素，它的值为0。
3. 递归计算表格中每个元素的值，该值表示从起始节点到该节点的最短路径长度。
4. 当结束时，结果将存储在表格的右下角元素中。

Tabulation方法可以大大简化动态规划问题的求解过程。它还可以更好地利用计算机内存，因为不需要存储所有子问题的解答。

条列重点

1. Tabulation 是一种资料处理方法，将资料整理成表格形式，方便分析和理解。

2. Tabulation 可以用于统计数据、调查结果、市场调查等领域。

3. Tabulation 要求资料清晰、一致和完整，这样才能正确地进行统计和分析。

4. Tabulation 的重点是资料的分类、标准化、整理和呈现。

5. Tabulation 的核心工具是电子表格软件，如 MS Excel、Google Sheets 等。

6. Tabulation 可以产生各种图表，如柱状图、折线图、饼图等，以更好地展示资料。

7. Tabulation 的应用范围广泛，可用于学术研究、商业分析、社会调查等不同领域。

8. 需要注意的是，Tabulation 只是一种分析工具，可以帮助分析资料，但不能替代对资料本身的理解和分析。

知识测验

1.问题：斐波那契数列的第 n 项是什么？
答案：1,1,2,3,5,8,13，…

2.问题：给定一个整数数组和一个目标值，找到数组中和为目标值的两个数字的索引。
答案：[0,1]

3.问题：给定一个非空字符串 s 和一个字典 wordDict ，判断 s 是否可以被空格拆分成一个或多个在字典中出现的单词。
答案：True

4.问题：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
答案：6 （从第一位开始，连续的子数组可为 [−2,1,−3,4,-1,2,1,-5,4]，最大连续子数组为 [4,-1,2,1]，其和为 6）

5.问题：给定两个单词 word1 和 word2，找到使得 word1 转换成 word2 所需的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符，删除一个字符，替换一个字符。
答案：3