题目描述： 方法1：动态规划，dp_max与dp_min 分别表示遍历 i 时，以 i 结尾的子数组最大乘积和最小乘积 class Solution { public: int maxProduct(vector<int>& nums) { int dp_max = nums

题目描述： 方法1：排列形式的完全背包问题 #include <iostream> #include <vector> using namespace std; int climb(int n,int m){ vector<int> dp(n+1,0); dp[0] = 1;

纯完全背包（题型1，3）考虑的是最大价值，所以不用管遍历顺序 求最小数（题型4）也不用管遍历顺序 01背包 二维初始化：j >= weight[0]时，dp[0][j] = value[0]，（题型1，3），dp[0][0]分情况讨论或dp[0][0] = 1，其余全0（题型2，参考目标和） 一维初

题目描述： 方法1：二维dp动态规划 dp[i][0]，表示第i天拥有股票最大收益 dp[i][1]，表示第i天没有股票最大收益 dp[i][0] = max(dp[i-1][0], -price[i]) 第i-1天就持有股票，那么就保持现状 第i天买入股票 dp[i][1] = max(dp[i-

题目描述： 方法1：排列形式的完全背包问题 class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int>dp(target+1,0); dp[

题目描述： 零钱兑换Ⅰ中，所求为凑满总金额需要最少的硬币个数 类似于目标和那道题，只不过那题是01背包问题（遍历顺序为从后往前），这题为完全背包问题 方法1：完全背包问题 本题和纯完全背包问题不同，纯完全背包考虑的是最大价值，所以不用管遍历顺序，本题是求装满的方式总数，得考虑题目要求是排列数还是组合

特点：01背包同一物品只能取一次，完全背包同一物品可以取多次 题目描述： 方法1：二维dp 与01背包不同点： dp数组第一行初始化时不同 递推时，放物品i时处理情况不同，dp[i - 1][j - weight[i]] + value[i]变为dp[i][j - weight[i]] + valu

题目描述： 方法1：回溯 class Solution { public: bool backtrack(string s,unordered_set<string> words,int StartIndex){//从StartIndex开始截取 if(StartIndex

题目描述： 方法1：回溯算法 方法2：动态规划 sum是固定的，target也是固定的，有式子left + right = sum，left - right = target，设left为背包容量，装满left背包的策略总数即为题解，left = (target + sum) / 2 初始dp[i]

题目描述： 方法1：转化为背包问题，把石头尽可能分成两堆，求两堆石头重量差最小值，进一步转化为，将石头放进容量为sum/2的背包中，最大价值为MaxValue，最后(sum - MaxValue) - MaxValue即为题解 class Solution { public: int las