这篇文章上次修改于 410 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序课算法笔记3——动态规划
问题一：HDOJ2084——数塔问题
问题描述：
有一个数塔，从顶部出发，要求找到一条从顶部到底部的一条路径，使路径上的和最大
解题思路：
如果去掉左上方一条或者右上方一条，就会变成新的塔，如果知道这两个新的塔的结果，就可以获取题目的答案。
将一个问题分解成了两个子问题。
自顶而下的分析，自底而上的计算。
状态转移方程：
dp[i][j]代表路径以i行第j个为起点的路径，路径的最大值（一开始储存了这个点的值）
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + dp[i][j]
问题二：HDOJ1176——免费馅饼
问题描述：
有 0-10个格子，每个时间点，都会有n个馅饼从天而降，会告诉你每个时间点n个煎饼的位置，假设人默认站在5位置开始，每一个时间都只能移动一格，求最大能捡到的煎饼数量
解题思路：
每个点都只有往下的三个选择，如果我先知道了往下的点能吃到的馅饼数量，就可以推出这个点
状态转移方程：
dp[j][i]代表了在第i时间，站在j位置的收获的最多馅饼数量（一开始有馅饼为1没有为0）
dp[j][i] = max(dp[j][i + 1], dp[j + 1][i + 1], dp[j - 1][i + 1]) + dp[j][i];
问题三：最长有序子序列（LIS）
问题描述：
给一个长度为n的数字序列，求最长的递增子序列长度
解题思路：
先排除掉暴力的念头
所有的最长子序列最后一个元素的情况只有n中（n是原序列长度）
找到所有以每个数作为结尾的序列的长度中最长的长度储存，最前面的可以很简单的找到。而后面的可以根据前面的获得到。问题已解，时间复杂度O(n2)
状态转移方程：
dp[i]代表了以第i个数作为结尾的递增子序列最长的长度。
dp[i] = max(dp[i],dp[j] + 1)，其中j是0到i-1之间的任意一个数，且nums[j] < nums[i]
当然，也有复杂度为O(N log N)的优化版
问题四：HDOJ1160——Fat Mouse ‘s speed
问题描述：
输入很多老鼠的重量和速度。输出n个老鼠的数量，n行表示编号，该编号的老鼠必须重量是递增的，速度是递减的。
解题思路：
和问题三类似
状态转移方程：
dp[i]代表了以第i个数作为结尾的递增子序列最长的长度。
dp[i] = max(dp[i],dp[j] + 1)，其中j是0到i-1之间的任意一个数，且weight[j] < weight[i] and speed[j] > speed[i]
问题五：HDOJ1087——super jump
问题描述：
给你一个数字序列，找到一条递增子序列，其所有点的和最大
进阶版LIS
解题思路：
和问题三类似
状态转移方程：
dp[i]代表了以第i个数作为结尾的递增子序列最大的路径值。初始为第 i 个数的值
dp[i] = max(dp[i],dp[j] + dp[i])，其中 j 是 0 到 i - 1 之间的任意一个数，且nums[j] < nums[i]
问题六：最长公共子序列
问题描述：
给你两个字符串，找到它们最长的相同子序列
解题思路：
寻找这个问题的子问题，对于两个字符串的最长公共长度，通过判断最后的两个字符，我们可以找到方程一，如果不相同，可以找到方程2
状态转移方程：
如果字符串1的第m个和字符串2的第n个相同
dp[m][n] = dp[m - 1][n - 1] + 1
否则
dp[m][n] = max(dp[m][n - 1], dp[m -1][n])
问题七：HDOJ1421——搬寝室
问题描述：
提供n和k，给n个数字，找到k对的数，使这k对数的差的平方和最小
解题思路：
选择的k对数字，每对数字都是大小排序后相邻的。前两个数和前四个数的选择方式
取一对
两个数，一种情况
三个数，有第三个和无第三个
四个数，有第四个和（三个数的情况）
n个数，有第n个和（n - 1个数的情况）
取k对
n个数取k对，分为 有第n个数（n - 2个数取 k - 1对 + 这对） 和 无第n个的（n - 1个数取k对）
状态转移方程：
dp[i][j]代表前 i 个数字取 j 对，最小的差的平方和
dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + S) S是最小的两个数字的差的平方和。
问题八：HDOJ1058——Humble Numbers
问题描述：
质数因子只有2、3、5或7的数称为谦卑数。序列1、2、3、4、5、6、7、8、9、10、12、14、15、16、18、20、21、24、25、27这是前20个谦卑数。
要求输入n，输出第n个谦卑数。
算法思路：
每个大的数都是由在数列里面小的数乘上 2， 3， 5，7
所以得到以下状态转移方程
dp[n] = min(dp[a1] * 2, dp[a2] * 3, dp[a3] * 5, dp[a4] * 7)
a1, a2, a3, a4分别代表了四个因数和其最小数（此最小数乘以这个因数要大于dp[n - 1]）
