概念理解

题型总结

丑数

264. 丑数 II
一个丑数是由2，3，5中的一个与前面已经得到的一个丑数相乘得来。
同类型的题目还有：313. 超级丑数,17.09. 第 k 个数

背包问题

01背包

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维数组
数组dp[i][j] =new int[N][W+1]

1. 确定dp数组以及下标的含义
   dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式
   dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 初始化
   dp[i][0] = 0
   遍历第一个物品的时候，对于大于value[0]的空间最多取到value[0]。

4. 遍历顺序：
   01背包二维dp数组在遍历顺序上，外层遍历物品 ，内层遍历背包容量和外层遍历背包容量 ，内层遍历物品都是可以的！

一维数组

1. 确定dp数组的定义:
   在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2. 确定递推公式
   dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 初始化
   dp[i][0] = 0

4. 遍历顺序：
   一定是外层for循环遍历物品，内层for循环遍历背包容，并且只能是从右向左遍历，目的是防止覆盖上一轮的遍历结果。

5. 核心代码

   for(int i = 0; i < weight.size(); i++) { // 遍历物品
       for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
           dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
       }
   }
   

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

二维数组

一维数组

1. 确定dp数组以及下标的含义
   dp[j]表示容量为i的背包，所背的物品价值可以最大为dp[j]。

2. 确定递推公式
   dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 初始化
   dp[i][0] = 0

4. 遍历顺序
   一维数组只能从左向右遍历，这样才能利用当前数在前面已经遍历的结果。

5. 核心代码

   for(int i = 0; i < weight.size(); i++) { // 遍历物品
       for(int j = weight[i]; j < bagWeight; j++) { // 遍历背包容量
           dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
       }
   }
   

组合数与排列数

组合不强调元素之间的顺序，排列强调元素之间的顺序

组合数案例: 凑出总金额x的货币总组合数、装满背包有多少种方法。题目有518. 零钱兑换 II
排列数案例：凑出目标数target的所有组合(顺序不同的序列被视作不同的组合)。题目有377. 组合总和 Ⅳ、70. 爬楼梯

外循环背包内循环物品能够穷尽某一背包容量下，物品的所有排列可能。
外循环物品内循环背包计算的是装满背包有多少种方法（组合）。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

不论是外循环还是内循环，循环背包都是循环dp[]数组，循环物品都是循环物品数组nums[]。

01背包与完全背包的对比

遍历顺序
01背包和完全背包唯一不同就是体现在遍历顺序上

对于二维dp数组
01背包：两个for循环嵌套顺序谁先谁后都可以
完全背包：两个for循环嵌套顺序谁先谁后都可以（如果问装满背包有几种方式的话？那么两个for循环的先后顺序就有很大区别了）

对于一维dp数组
01背包：一定是外层for循环遍历物品，内层for循环遍历背包容，并且只能是从右向左遍历，目的是防止覆盖上一轮的遍历结果。
完全背包：两个for循环嵌套顺序仍然无所谓，一维数组只能从左向右遍历，这样才能利用当前数在前面已经遍历的结果。（如果问装满背包有几种方式的话？那么两个for循环的先后顺序就有很大区别了）

一维数组、二维数组
多用一维数组，节省空间

子数组 子字符串

• AAA413. 等差数列划分
• AAAA5229. 拼接数组的最大分数
  是53题的拓展，求出差集的子数组最大和，然后与对应数组的和相加，两个数组都这样做，取较大的那个。
• AAAA313. 超级丑数
  丑数II的拓展，取质数与各自当前超级丑数乘积的最小值。
• AAA467. 环绕字符串中唯一的子字符串
  计算出以x字母为结尾的最长子字符串就能得到所有以x结尾的子字符串的个数。

序列问题

• AAAA*368. 最大整除子集
  为了得到子集而不是子集的长度，需要另外定义一个数组，标记当前结点是怎么到来的。
• 0AAAA940. 不同的子序列 II
  遍历字符串，以每个字母为结尾计算子序列的个数，不会产生重复子序列。

石子合并问题

• **石子合并问题-合并金币
  每次遍历数组寻找和最小的两个临界数然后求和合并，这个思路行不通。把求和看成在i,j之间劈一刀，然后把这两半合并，i~j之间有j-i种切分可能，选择合并之后和最小的那种。

记忆化搜索

• *375. 猜数字大小 II
  每次猜是哪个数字能够让花掉的钱最少？猜这个数的时候最少要准备多少钱才能确保能够猜中。

路径问题

• *576. 出界的路径数
  求在step步之内，一个节点到边界出轨的路径个数，等于在step-1步之内，这个节点四周的节点的到边界出轨的路径个数之和。
• AAA*6059. 检查是否有合法括号字符串路径
  想到用一个变量表示左右括号合理状态，用这个变量表示起始节点到当前节点的合理状态。
• AAAA*673. 最长递增子序列的个数
  使用额为的数组记录以当前元素为结尾的最长上升子序列的个数
• 0AAAA764. 最大加号标志
  分别计算四个方向上的k值，当前值可以通过它前面(/下面/右面/左面)的值得到。

台阶问题

• AAA403. 青蛙过河
  理解题目意思找到动态转移方程。相比于传统跳台阶，跳法复杂了。
• AAAAA6100. 统计放置房子的方式数
  还没理解动态规划为什么这么做是正确的
• 0AAAA790. 多米诺和托米诺平铺
  当前第n个列的方块个数分为四种状态,当前状态取决于第n-1列的状态.

状态DP 打家劫舍

• AAA740. 删除并获得点数
  打家劫舍4的变种
• AAAA801. 使序列递增的最小交换次数
  根据每个位置可能交换，也可能不交换，因此设一个二维数组dp[i][2]，第一维表示位置，第二维表示是否交换。

区间问题(区间作业收益最大化问题)

根据区间的右端点给区间排序，计算以每一个区间为结尾的最大收益。

• 0AAAA1235. 规划兼职工作
• 0AAAA2008. 出租车的最大盈利

其他

• 1025. 除数博弈
  可以通过已知部分推导出来，那就用动态规划去解决。
• AAA1014. 最佳观光组合
  遍历数组，考虑每一个元素是右边的j，然后更新两部分和的最大值
• AAAA1024. 视频拼接
  所有包含了当前秒的素材都遍历一下，选出从0到i需要素材最少的那个素材。

解体技巧

状态

题目个体有多个状态，用二维数组表示，第一维表示个体，第二维表示状态，如果状态少，可以用多个一维数组表示各个状态。状态的维度不同时，增加数组的维数，如188. 买卖股票的最加时机IV

• AAAA926. 将字符串翻转到单调递增
  根据结果的状态创建二维甚至更高维的数组，目的是能够区分状态。
• AAA1567. 乘积为正数的最长子数组长度
  用两个数组分别表示乘积是正数和负数的状态，方便推导正负乘积。
• AAAA122. 买卖股票的最佳时机 II
  用数组的第二维表示股票持有状态。买股票时，继承了历史收益。
• AAAA188. 买卖股票的最加时机IV
  用数组的第二维表示第几次买卖股票，第三维表示股票持有状态。

最后

以上就是细心铃铛为你收集整理的动态规划-题目总结概念理解题型总结解体技巧的全部内容，希望文章能够帮你解决动态规划-题目总结概念理解题型总结解体技巧所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。