动态规划在面试中常被考察，下面总结了一些经典题型供参考。

强盗抢劫

题目：强盗在一系列房间中抢钱，不能抢相邻的房间，求最大抢钱数。数组示例：[2,7,9,3,1]

思路：使用动态规划，状态转移方程为 dp[i] = max(dp[i-2]+nums[i], dp[i-1])。从后向前计算，最终结果为 dp[n-1]。

跳台阶

题目描述：有 N 阶楼梯，每次可上一阶或两阶，求有多少种上楼梯的方法。

思路：斐波拉切数列，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。从后向前计算，最终结果为 dp[N]。

矩形最小路径和

题目：给定一个包含非负整数的 m x n 网格，求从左上角到右下角的路径，使得路径上数字总和最小。输入:[[1,3,1], [1,5,1], [4,2,1]] 输出: 7。

动态方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + nums[i][j]。从左上角开始遍历，最终结果为 dp[m-1][n-1]。

划分数组为两个相等的子集

题目：输入：[1, 5, 11, 5]，输出：[1, 5, 5]和[11]。

思路：寻找数组中能组成目标和的一半的元素，利用动态规划记录是否存在组合。

乘积最大连续子数组

题目：输入一个整形数组，数组里有正数也有负数。求所有子数组的和的最大值。例如数组：arr[]={1, 2, 3, -2, 4, -3 }，最大子数组为 {1, 2, 3, -2, 4}，和为8。

动态方程：fmax(i) = max(nums[i], fmax(i-1) * nums[i])，fmin(i) = min(nums[i], fmin(i-1) * nums[i])。分别计算最大和最小乘积，更新最大值。

等差递减区间的个数

题目：求一个数组中等差递减区间个数，等差数列必须是连续的。例子：A = [1, 2, 3, 4]，个数为3，分别是: [1, 2, 3], [2, 3, 4]。

动态方程：dp[i] = dp[i-1] + (nums[i] - nums[i-1] == 1)。计算每个元素结尾的连续递减序列数量。

最长回文子串

题目：求最长回文子串。输入: "babad"，输出: "bab" 或者 "aba"。

动态规划方程：dp[i][j] = (s[i] == s[j] && (j - i < 3 || dp[i+1][j-1]))。从中心向两边扩展，寻找最长回文子串。

最长递增子序列

题目：求一个数组的最长自增子序列。输入: [10,9,2,5,3,7,101,18]，输出: 4。

动态规划方程：dp[i] = max(dp[i], dp[j]+1)。计算以每个元素结尾的最长递增子序列长度。

最大子序和

题目：给定一个整数数组 nums ，找到具有最大和的连续子数组。输入: [-2,1,-3,4,-1,2,1,-5,4]，输出: 6。

动态方程：dp[i] = max(nums[i], dp[i-1]+nums[i])。计算以每个元素结尾的连续子数组最大和。