一、动态规划知识
1. 动态规划概念
略
二、知识扩展
1. 基础
知识扩展
略
题目练习
Ⅰ：爬楼梯的最少成本
题目描述
一个数组 cost 的所有数字都是正数，它的第 i 个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本 cost[i] 之后可以从第 i 级台阶往上爬 1 级或 2 级。假设台阶至少有 2 级，既可以从第 0 级台阶出发，也可以从第 1 级台阶出发，请计算爬上该楼梯的最少成本。例如，输入数组 [1，100，1，1，100，1]，则爬上该楼梯的最少成本是 4，分别经过下标为 0、2、3、5 的这 4 级台阶，如图 13.1 所示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
2. 单序列问题
知识扩展
略
题目练习
Ⅰ：房屋偷盗
题目描述
输入一个数组表示某条街道上的一排房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取到多少财产。例如，街道上 5 幢房屋内的财产用数组 [2，3，4，5，3] 表示，如果小偷到下标为 0、2 和 4 的房屋内盗窃，那么他能偷取到价值为 9 的财物，这是他在不触发报警系统的情况下能偷取到的最多的财物，如图 13.2 所示。被盗的房屋上方用特殊符号标出。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅱ：环形房屋偷盗
题目描述
一条环形街道上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取的财产的数量。例如，街道上 5 家的财产用数组 [2，3，4，5，3] 表示，如果小偷到下标为 1 和 3 的房屋内盗窃，那么他能偷取到价值为 8 的财物，这是他在不触发报警系统的情况下能偷取到的最多的财物，如图 13.3 所示。被盗的房屋上方用特殊符号标出。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅲ：粉刷房子
题目描述
一排n幢房子要粉刷成红色、绿色和蓝色，不同房子被粉刷成不同颜色的成本不同。用一个 n×3 的数组表示 n 幢房子分别用 3 种颜色粉刷的成本。要求任意相邻的两幢房子的颜色都不一样，请计算粉刷这 n 幢房子的最少成本。例如，粉刷 3 幢房子的成本分别为 [17，2，16]，[15，14，5]，[13，3，1]，如果分别将这 3 幢房子粉刷成绿色、蓝色和绿色，那么粉刷的成本是 10，是最少的成本。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅳ：翻转字符
题目描述
输入一个只包含 '0' 和 '1' 的字符串，其中，'0' 可以翻转成 '1'，'1' 可以翻转成 '0'。请问至少需要翻转几个字符，才可以使翻转之后的字符串中所有的 '0' 位于 '1' 的前面？翻转之后的字符串可能只包含字符 '0' 或 '1'。例如，输入字符串 "00110"，至少需要翻转一个字符才能使所有的 '0' 位于 '1' 的前面。可以将最后一个字符 '0' 翻转成 '1'，得到字符串 "00111"。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅴ：最长斐波那契数列
题目描述
输入一个没有重复数字的单调递增的数组，数组中至少有 3 个数字，请问数组中最长的斐波那契数列的长度是多少？例如，如果输入的数组是 [1，2，3，4，5，6，7，8]，由于其中最长的斐波那契数列是 1、2、3、5、8，因此输出是 5。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅵ：最少回文分割
题目描述
输入一个字符串，请问至少需要分割几次才可以使分割出的每个子字符串都是回文？例如，输入字符串 "aaba"，至少需要分割 1 次，从两个相邻字符 'a' 中间切一刀将字符串分割成两个回文子字符串 "a" 和 "aba"。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
3. 双序列问题
知识扩展
略
题目练习
Ⅰ：最长公共子序列
题目描述
输入两个字符串，请求出它们的最长公共子序列的长度。如果从字符串 s1 中删除若干字符之后能得到字符串 s2，那么字符串 s2 就是字符串 s1 的一个子序列。例如，从字符串 "abcde" 中删除两个字符之后能得到字符串 "ace"，因此字符串 "ace" 是字符串 "abcde" 的一个子序列。但字符串 "aec" 不是字符串 "abcde" 的子序列。如果输入字符串 "abcde" 和 "badfe"，那么它们的最长公共子序列是 "bde"，因此输出 3。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅱ：字符串交织
题目描述
输入 3 个字符串 s1、s2 和 s3，请判断字符串 s3 能不能由字符串 s1 和 s2 交织而成，即字符串 s3 的所有字符都是字符串 s1 或 s2 中的字符，字符串 s1 和 s2 中的字符都将出现在字符串 s3 中且相对位置不变。例如，字符串 "aadbbcbcac" 可以由字符串 "aabcc" 和 "dbbca" 交织而成，如图 13.4 所示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅲ：子序列的数目
题目描述
输入字符串 S 和 T，请计算字符串 S 中有多少个子序列等于字符串 T。例如，在字符串 "appplep" 中，有 3 个子序列等于字符 串 "apple"，如图 13.5所示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
4. 矩阵路径问题
知识扩展
略
题目练习
Ⅰ：路径的数目
题目描述
一个机器人从 m×n 的格子的左上角出发，它每步要么向下要么向右，直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目。例如，如果格子的大小是 3×3，那么机器人从左上角到达右下角有 6 条符合条件的不同路径，如图 13.6 所示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅱ：最小路径之和
题目描述
在一个 m×n(m、n 均大于 0) 的格子中，每个位置都有一个数字。一个机器人每步只能向下或向右，请计算它从格子的左上角到达右下角的路径的数字之和的最小值。例如，从图 13.7 中 3×3 的格子的左上角到达右下角的路径的数字之和的最小值是 8，图中数字之和最小的路径用灰色背景表示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅲ：三角形中最小路径之和
题目描述
在一个由数字组成的三角形中，第 1 行有 1 个数字，第 2 行有 2 个数字，以此类推，第 n 行有 n 个数字。例如，图 13.8 是一个包含 4 行数字的三角形。如果每步只能前往下一行中相邻的数字，请计算从三角形顶部到底部的路径经过的数字之和的最小值。如图 13.8 所示，从三角形顶部到底部的路径数字之和的最小值为 11，对应的路径经过的数字用阴影表示。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
4. 背包问题
知识扩展
略
题目练习
Ⅰ：分割等和子集
题目描述
给定一个非空的正整数数组，请判断能否将这些数字分成和相等的两部分。例如，如果输入数组为 [3，4，1]，将这些数字分成 [3，1] 和 [4] 两部分，它们的和相等，因此输出 true；如果输入数组为 [1，2，3，5]，则不能将这些数字分成和相等的两部分，因此输出 false。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅱ：加减的目标值
题目描述
给定一个非空的正整数数组和一个目标值 S，如果为每个数字添加 + 或 - 运算符，请计算有多少种方法可以使这些整数的计算结果为 S。例如，如果输入数组 [2，2，2] 并且 S 等于 2，有3种添加 + 或 - 的方法使结果为 2，它们分别是 2+2-2=2、22+2=2 及 -2+2+2=2。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅲ：最少的硬币数目
题目描述
给定正整数数组 coins 表示硬币的面额和一个目标总额 t，请计算凑出总额 t 至少需要的硬币数目。每种硬币可以使用任意多枚。如果不能用输入的硬币凑出给定的总额，则返回 -1。例如，如果硬币的面额为 [1，3，9，10]，总额 t 为 15，那么至少需要 3 枚硬币，即 2 枚面额为 3 的硬币及 1 枚面额为 9 的硬币。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅳ：排列的数目
题目描述
给定一个非空的正整数数组 nums 和一个目标值 t，数组中的所有数字都是唯一的，请计算数字之和等于t的所有排列的数目。数组中的数字可以在排列中出现任意次。例如，输入数组 [1，2，3]，目标值 t 为 3，那么总共有 4 个组合的数字之和等于 3，它们分别为 {1，1，1}、{1，2}、{2，1} 及 {3}。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
三、章节小结
略