张家港网站建设培训班,电商seo引流,wordpress改手机布局,深圳市住房和建设局网站首页动态规划
一、一维数组#xff1a;斐波那契数列 爬楼梯70简单 dp定义#xff1a; dp[i]表示爬到第i阶有多少种不同的方式 状态转移方程#xff1a; dp[i] dp[i-1] dp[i-1] #xff08;每次可以爬1或2个台阶#xff09; 边界条件#xff1a; dp[0] 1; dp[1] 1;#…动态规划
一、一维数组斐波那契数列 爬楼梯70简单 dp定义 dp[i]表示爬到第i阶有多少种不同的方式 状态转移方程 dp[i] dp[i-1] dp[i-1] 每次可以爬1或2个台阶 边界条件 dp[0] 1; dp[1] 1;满足dp[2] 2 返回值 dp[n]即通过累积dp[n]为爬到第n阶台阶的方式 改进 因为dp只使用了前两个值所以使用两个变量存储两个值不断迭代更新。——试过之后与原dp数组相比改进不大可能是因为题中n的值比较小如果n的值较大的话会节省空间开销。 打家劫舍198中等 dp定义 dp[i]表示打劫到第i间房屋能偷窃到的最高金额 状态转移方程 dp[i] max(dp[i-1], dp[i-2] 第i间房屋的金额) 边界条件 dp[0] 0; dp[1] nums[0]; (后续 要计算dp[i-2]) 返回值 dp[n]即打劫到第n间房屋能偷窃到的最高金额 改进 同样可以缩小空间开销在数组够长的时候可以进行节省。 打家劫舍Ⅱ213中等 该题在上一题的基础上加了一个限制条件房屋是环形也就是在偷了第一间房的情况下不能偷最后一间偷了最后一间的情况下不能偷第一间 所以分为两种情况从第1间到第n-1间从第2间到第n间。 dp定义 dp[i]表示打劫到第i间房屋能偷窃到的最高金额 状态转移方程 dp[i] max(dp[i-1], dp[i-2] 第i间房屋的金额) 边界条件 只有一间房屋返回该房屋的金额只有两间房屋返回两间房屋中金额最大的超过两间根据特殊情况分别计算抢劫第1间房屋和最后一间房屋两种情况下能获取到的最高金额将其返回。 返回值 盗窃金额最高的情况 改进 节省空间开销
总结以上情况均使用了一维dp数组且状态转移方程与数组的前几个数有关可以使用变量存储节省空间开销。关键对dp[i]的定义明确状态转移方程确定好在这种情况下再对边界情况进行特殊考虑。
二、二维数组矩阵路径 矩阵的最小路径和64中等 dp定义 dp[i][j]表示移动到[i][j]位置的时候路径上的数字和最小 状态转移方程 dp[i][j] min(dp[i-1][j] [i][j]位置的数字, dp[i][j-1] [i][j]位置的数字) 边界条件 第一行[i][j-1], 第一列[i-1][j] 返回值 dp[m][n] 题目给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。
输入grid [[1,3,1],[1,5,1],[4,2,1]]
输出7
解释因为路径 1→3→1→1→1 的总和最小。
示例 2输入grid [[1,2,3],[4,5,6]]
输出12 class Solution {
public:int minPathSum(vectorvectorint grid) {int raw grid.size();int col grid[0].size();vectorvectorint dp(raw, vectorint(col, 0));dp[0][0] grid[0][0];for (int j 1; j col; j) {dp[0][j] dp[0][j-1] grid[0][j];}for (int i 1; i raw; i) {dp[i][0] dp[i-1][0] grid[i][0];}// 遍历for (int i 1; i raw; i) {for (int j 1; j col; j) {dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j];}}return dp[raw-1][col-1];}
};改进 空间优化相当于对矩阵进行了压缩 class Solution {
public:int minPathSum(vectorvectorint grid) {int raw grid.size();int col grid[0].size();vectorint dp(col);// 初始化dp[0] grid[0][0];for (int i 1; i col; i) {dp[i] dp[i-1] grid[0][i];}for (int i 1; i raw; i) {dp[0] dp[0] grid[i][0];for (int j 1; j col; j) {dp[j] min(dp[j-1] grid[i][j], dp[j] grid[i][j]);}}return dp[col-1];}
};不同路径62中等 dp定义 dp[i][j]表示到[i][j]位置的路径总数 状态转移方程 dp[i][j] dp[i-1][j] dp[i][j-1] 边界条件 dp[0][j] 1; dp[i][0] 1 返回值 dp[m-1][n-1] 改进 和上一题一样的思路
三、数组区间 数组区间和303简单 dp定义 dp[i]表示从0-i的元素和 状态转移方程 dp[i] dp[i-1] nums[i] 边界条件 dp[0] 0 返回值 dp[right] - dp[left] nums[left] 改进 这种情况下dp[right] - dp[left]之后包右不包左 数组中等差递增子区间的个数 dp定义 dp[i]是i位置等差数列的个数需要一个变量count记录到i位置之前等差数列的个数 状态转移方程 如果公差还为ddp[i] dp[i-1] 1; 如果方差变化d nums[i] - nums[i-1] 边界条件 d nums[i] - nums[i-1], dp[0] 0 返回值 count 改进 nums[i] - nums[i-1] nums[i-1] - nums[i-2] 隐含了判断等差数列的长度大于等于3 改进代码 class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();// 长度必须大于3所以如果数列长度小于3返回0if (n 3) {return 0;}vectorint dp(n);dp[0] 0;dp[1] 0;// 等差数列个数int count 0;for (int i 2; i n; i) {if (nums[i] - nums[i-1] nums[i-1] - nums[i-2]) {dp[i] dp[i-1] 1;count dp[i];}}return count;}
};四、分割整数 分割整数的最大乘积343 dp定义 dp[i] 表示第i个数拆分后可以得到的最大乘积会成为后面数的因数。 状态转移方程 i表示当前要计算最大乘积的数j表示i的某个因数 for (int i 2; i n; i) {int curMax 0;for (int j 1; j i; j) {curMax max(curMax, max(j* (i-j), j * dp[i-j]));}dp[i] curMax;
}边界条件 拆分的正整数的个数大于2所以dp[0] 0; dp[1] 1 返回值 dp[n] 改进 按平方数来分割整数279中等 dp定义 dp[i]表示i的完全平方数的最小数量 状态转移方程 for (int i 1; i n; i) {int minValue INT_MAX;for (int j 1; j * j i; j) {minValue min(minValue, dp[i-j*j]);}dp[i] minValue 1;
}边界条件 dp[0] 0 返回值 dp[n] 改进 分割整数构成字母字符串91中等 dp定义 dp[i]表示0-i位置有的编码方式 状态转移方程 因为26个字母编码有两位数而且前缀0是不能包含在两位数的所以分为两种情况 第一种是只把加第i个数当成编码 if (s[i-1] ! 0) {dp[i] dp[i-1];}第二种加上前一个数看是否构成新的编码 if (s[i-2] ! 0 ((s[i-2] - 0) * 10 (s[i-1] - 0)) 26) {dp[i] dp[i-2];
}边界条件 dp[0] 1; 返回值 dp[n] 改进
五、最长递增子序列 最长递增子序列300中等 dp定义 dp[i]表示从0-i可以构成递增子序列的最大长度 状态转移方程 因为可以删除数组中的某些元素所以递增子序列要从之前的所有数检查。 for (int i 0; i n; i) {dp[i] 1;for (int j i - 1; j 0; j--) {if (nums[j] nums[i]) {dp[i] max(dp[i], dp[j] 1);}}
}边界条件 dp[i] 1每个元素都是一个递增子序列 返回值 dp数组中的最大值。 改进 贪心二分查找 贪心因为我们想要上升子序列尽可能长所以就要序列上升得尽可能慢每次在上升子序列最后加上的数尽可能小 dp定义dp[i]表示长度为i的最长上升子序列的末尾元素的最小值用len记录目前最长上升子序列的长度起始为1 状态转移方程 if (nums[i] d[len]) {d[len] nums[i];
} else {// 二分查找int l 1, r len, pos 0;while (l r) {int mid (l r) 1;if (d[mid] nums[i]) {pos mid;l mid 1;} else {r mid - 1;}}d[pos 1] nusm[i];-0
} 边界条件dp[1] nums[0]; 返回值len 一组整数对能够构成的最长链646中等 dp定义 dp[i]表示以pairs[i]为结尾的最长数对链的长度 状态转移方程 先将数对链的第一个元素进行排序以第i位为定点遍历之前一共可以组成多少个数对链 sort(pairs.begin(), pairs.end());
for (int i 0; i n; i) {for (int j 0; j i; j) {if (pairs[i][0] pairs[j][1]) {dp[i] max(dp[i], dp[j] 1);}}
}边界条件 无 返回值 dp[n-1] 改进 按元组的第二个数的大小进行排序 最长摆动子序列376中等 dp定义 两个dp分别定义上升序列up和下降序列down 状态转移方程 如果差是正up序列更新如果差是负down序列更新如果差为0都不更新。 up[0] down[0] 1;
for (int i 1; i n; i) {if (nums[i] nums[i-1]) {up[i] max(up[i-1], down[i-1] 1);down[i] down[i-1];} else if (nums[i] nums[i-1]) {down[i] max(down[i-1], up[i-1] 1);up[i] up[i-1];} else {up[i] up[i-1];down[i] down[i-1];}
}边界条件 up[0] down[0] 1; 返回值 max(down[i-1], up[i-1]); 改进 减少空间消耗使用up和down两个变量进行存储 int up 1, dowm 1
for (int i 1; i n; i) {if (nums[i] - nums[i-1] 0) {down 1;} else if (nums[i] - nums[i-1] 0){up 1;}
}
return max(up, down);六、最长公共子序列 最长公共子序列1143中等 dp定义 dp[i][j]表示word1的第i位和word2的第j位之前序列的最长公共子序列 状态转移方程 如果word1[i] word2[j], dp[i][j] dp[i-1][j-1] 1 如果word1[i] ! word2[j], dp[i][j] max(dp[i-1][j], dp[i][j-1]) 边界条件 dp[0][0] 0 返回值 dp[n][m] 改进
七、0-1背包 划分数组为和相等的两部分416中等 dp定义 dp[i][j]表示到nums数组的第i个位置和能否是jtrue表示和可以是jfalse表示不可以 状态转移方程 如果j 当前数nums[i]说明不能放入dp[i][j] dp[i-1][j] 如果j 当前数nums[i]有两种情况dp[i][j] dp[i-1][j] | dp[i-1][j-nums[i]] 边界条件 和为0哪个元素都不选dp[i][0] true dp[0][nums[0]] true 返回值 dp[n-1][target] 改进 空间优化 改变一组数的正负号使得它们的和为一给定数494中等 —— 回溯递归 应该想法简单一点不能把全过程都想清楚把子问题想明白就行 dp定义 状态转移方程 边界条件 返回值 改进 01字符构成最多的字符串474中等——三维数组 dp定义 dp[i][j][k]三维dp数组第一维表示在前多少个字符串中找0和1j表示0的个数k表示1的个数。 状态转移方程 for (int i 1; i length; i) {// 计算该字符串中0和1的个数for (int j 0; j m; j) {for (int k 0; k n; k) {dp[i][j][k] dp[i-1][j][k];if (j zeros k ones) {dp[i][j][k] max(dp[i][j][k], dp[i-1][j-zeros][k-ones] 1);}}}
}边界条件 dp[0][j][k] 0 返回值 dp[length][m][n] 改进 找零钱的最少硬币数322中等 dp定义 dp[i]表示金额和为i的最小硬币的数量 状态转移方程 for (int i 1; i amount; i) {for (int j 0; j coins.size(); j) {if (coins[j] i) {dp[i] min(dp[i], dp[i-coins[j]] 1);}}
}
if (dp[amount] amount) {return -1;
}
return dp[amount];边界条件 dp[0] 0dp[other] amount 1(表示没有构成amount金额的方案); 返回值 如果硬币不能构成所需金额则返回-1如果硬币可以构成所需金额返回所需的最小硬币数。 改进 找零钱的硬币数组合518中等 dp定义 dp[i]表示和为i的总方案数 状态转移方程 for (int i 1; i amount; i) {for (int j 0; j coins.size(); j) {if (i coins[j]) {dp[i] dp[i-coins[j]] 1;}}
}
return dp[amount];边界条件 dp[0] 0 返回值 dp[amount] 改进 字符串按单词列表分割139中等 dp定义 dp[i]表示截止i位置前的字符串是否可以有wordDict中的单词构成 将wordDict进行去重是因为可以减小重复计算 状态转移方程 vectorbool dp(s.size() 1);
for (int i 1; i size(); i) {for (int j 0; j i; j) {if (dp[j] wordDictSet.find(s.substr(j, i - 1)) ! wordDictSet.end()) {dp[i] true;break;}}
}边界条件 dp[0] true 返回值 dp[s.size()] 改进 组合总和377组合总和Ⅳ dp定义 dp[i] 表示和为i时的元素组合个数 状态转移方程 for(int i 1; i target; i) {for (int j 0; j nums.size(); j) {if (i nums[j] dp[i - nums[j]] INT_MAX - dp[i]) {dp[i] dp[i - nums[j]];}}
}边界条件 dp[0] 1 返回值 dp[target] 改进
八、股票交易
允许的交易次数
能否在同一天进行买卖
增加限制条件要增加维度 股票交易Ⅰ 121简单 dp定义 最简单的情况只有一个限制是不能在同一天进行买卖只进行一次交易dp[i]表示第i天卖出能获得的最大利润 状态转移方程 dp[i] max(dp[i-1], prices[i] minprices) 边界条件 dp[0] 0; 返回值 dp[n] 改进 空间优化两个变量buy和sell分别保存 int buy -prices[0];
int sell 0;
for (int i 1; i n; i) {buy max(buy, -prices[i]);sell max(sell, buy prices[i]);
}股票交易Ⅱ 122中等 没有限制交易次数 可以在同一天进行买卖 dp定义 dp[i][j]表示第i天的买入j0可以获得的最大利润和第i天卖出j1可以获得的最大利润 状态转移方程 dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]); dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]); 边界条件 dp[0][0] -prices[0]; dp[0][1] 0; 返回值 dp[n-1][1] 改进 空间优化 int buy -prices[0];
int sell 0;
for (int i 1; i n; i) {// int temp_buy max(buy, sell - prices[i]);// int temp_sell max(sell, buy prices[i]);// buy temp_buy;// sell temp_sell;// 第二种// int temp_buy buy;// int temp_sell sell;// buy max(temp_buy, temp_sell - prices[i]);// sell max(temp_sell, temp_buy prices[i]);// 第三种buy max(buy, sell - prices[i]);sell max(sell, buy prices[i]);
}
return sell;股票交易Ⅲ123困难 两次交易 允许同一天买卖 dp定义 dp[i][j]表示第i天的利润j0表示第一次买入j1表示第一次卖出j2表示第二次买入j3表示第二次卖出 状态转移方程 dp[i][0] max(dp[i-1][0], -prices[i]); dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]); dp[i][2] max(dp[i-1][2], dp[i-1][1] - prices[i]); dp[i][3] max(dp[i-1][3], dp[i-1][2] prices[i]); 边界条件 dp[0][0] -prices[0]; dp[0][2] -prices[0]; 返回值 dp[n-1][3] 改进 空间优化 for (int i 1; i n; i) {// 第一种// int temp_buy1 buy1;// int temp_sell1 sell1;// int temp_buy2 buy2;// int temp_sell2 sell2;// buy1 max(temp_buy1, -prices[i]);// sell1 max(temp_sell1, temp_buy1 prices[i]);// buy2 max(temp_buy2, temp_sell1 - prices[i]);// sell2 max(temp_sell2, temp_buy2 prices[i]);// 第二种buy1 max(buy1, -prices[i]);sell1 max(sell1, buy1 prices[i]);buy2 max(buy2, sell1 - prices[i]);sell2 max(sell2, buy2 prices[i]);
}股票交易Ⅳ188困难 K次交易 允许同一天进行买卖 dp定义 定义dp数组i表示第i天k表示完成了k次交易j有两个状态1表示手中持有股票0表示手中没有股票 状态转移方程 // 状态转移
for (int i 1; i n; i) {for (int K 1; K k; K) {dp[i][K][0] max(dp[i-1][K][0], dp[i-1][K-1][1] prices[i]);dp[i][K][1] max(dp[i-1][K][1], dp[i-1][K][0] - prices[i]);}
}边界条件 // 初始化
for (int i 0; i k; i) {dp[0][i][0] 0;dp[0][i][1] -prices[0];
}
for (int i 1; i n; i) {dp[i][0][0] 0;dp[i][0][1] max(dp[i-1][0][1], dp[i-1][0][0] - prices[i]);
}返回值 dp[n-1][k][0] 改进 需要冷却期的股票交易309中等 没有限制交易次数 允许同一天进行买卖但是卖掉之后要有一天冷冻期在冷冻期内不能买入股票 dp定义 dp[i][j], j的范围是0, 1, 2分别表示i位置买入卖出、冷冻的最大利润 状态转移方程 dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]) dp[i][2] max(dp[i-1][2], dp[i-1][1]) 边界条件 dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; 返回值 max(dp[n][0], max(dp[n][1], dp[n][2])); 改进 空间优化因为只用到了i-1时候的利润所以可以减小一个维度用三个变量来存储上一次买入、卖出、冷冻的最大利润 int n prices.size();
// 初始化
int get -prices[0];
int out 0;
int no 0;
for (int i 1; i n; i) {// 第一种// int temp_get get;// int temp_out out;// int temp_no no;// get max(temp_get, temp_no - prices[0]);// out max(temp_out, temp_get prices[0]);// no max(temp_no, temp_out);// 第二种冷冻期只有上一天卖出之后的后一天为冷冻期int temp_out out;get max(get, no - prices[i]);out get prices[i];no max(temp_out, no);
}需要交易费用的股票交易714中等 dp定义 dp[i][j]表示到第i支股票时j0时表示买入的利润j1时表示卖出的利润 状态转移方程 dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i] - fee) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]) 边界条件 dp[0][0] -prices[i] - fee 返回值 dp[n][1] 改进 空间优化因为只用到了前一天的买入、卖出的值所以只需要两个变量进行存储 int get -prices[0] - fee;
int out 0;
for (int i 1; i n; i) {// 第一种// int temp_get get;// int temp_out out;// get max(temp_get, temp_out - prices[i] - fee);// out max(temp_out, temp_get prices[i]);// 第二种get max(get, out - prices[i] - fee);out max(get prices[i], out);
}九、字符串编辑
1. 删除两个字符串的字符使他们相等583
本质二维DP
dp定义 dp[i][j]表示word1的i位置和word2的j位置最长公共子序列的长度删除操作数为两个字符串的长度和减去两倍最长公共子序列的长度
状态转移方程
if (word1[i-1] word2[j-1]) {dp[i][j] dp[i-1][j-1] 1;
} else {dp[i][j] max(dp[i-1][j], dp[i][j-1]);
}边界条件 dp[0][j] 0; dp[i][0] 0;
返回值 (n m) - 2 * dp[n][m]
改进
2. 编辑距离72困难
dp定义 dp[i][j]表示word1的第i个位置与word2的第j个位置相同的话需要的最少操作数行表示插入列表示删除对角线表示
状态转移方程
for (int i 1; i n; i) {for (int j 1; j m; j) {if (word1[i-1] word2[j-1]) {dp[i][j] dp[i-1][j-1];} else {dp[i][j] min(dp[i-1][j], dp[i][j-1]) 1;}}
}边界条件 dp[i][0] i表示删除dp[0][j] j表示插入。
返回值 dp[n][m]
改进
3. 复制粘贴字符650中等
dp定义 dp[i]表示能够打印i个’A’的最少操作次数
状态转移方程
for (int i 2; i n; i) {dp[i] INT_MAX;for (int j 1; j * j i; j) {if (i % j 0) {dp[i] min(dp[i], min(dp[i / j] j, dp[j] i / j));}}
}边界条件 dp[1] 0
返回值 dp[n]
改进
主要是思想的一些记录~
