如果网站不备案,wordpress时间线,如何写一个可以做报价计算的网站,第一次做ppt怎么弄在进行算法题练习和一些题目中发现关于动态规划的内容较多#xff0c;觉得有必要系统的学习和练习一下 于是参照bilbilUP主 英雄哪里出来 的动态规划50题和LeetKoke网站进行学习和练习
一 概述 动态规划 是一个有限状态自动机 可以抽象为一个有向无环图 有起始节点 终止节点 … 在进行算法题练习和一些题目中发现关于动态规划的内容较多觉得有必要系统的学习和练习一下 于是参照bilbilUP主 英雄哪里出来 的动态规划50题和LeetKoke网站进行学习和练习
一 概述 动态规划 是一个有限状态自动机 可以抽象为一个有向无环图 有起始节点 终止节点 每一个节点表示一个状态 任何一个非初始节点都可以从其他节点转移过来(状态转移) 而如何设计状态就是解决动态规划问题的关键 本质是空间换时间 利用空间的缓存能力来换取计算机的CPU消耗 最简单的例子就是递归(斐波那契数列) 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1 给定n 求f(n)的值int fib(int n) {if(n 0){return 0;}else if(n 1){return 1;}return fib(n-1) fib(n-2);} 二 解题步骤 设计状态确定状态转移方程确定初始状态执行状态转移计算最终的解 三 动态规划使用的判断 节点抽象后 关系用边表示 简单进行一次拓扑排序 如何发现有环 则一定不是动态规划 同样 动态规划问题也和数据范围有关系 如果数据量比较大 大概率不是动态规划(因为无法映射到数组中) 就有可能是暴力搜素或者贪心算法[动态规划靠经验] 四 相关题解
1 线性DP [1] 递推 (1) 青蛙跳台阶问题 一只青蛙一次可以跳上1级台阶也可以跳上2级台阶求该青蛙跳上一个n级的台阶总共有多少种跳法 答案需要取模1e97(1000000007) 如计算初始结果为100000008 请返回1 #define mod 1000000007int f[110];int numWays(int n) {f[0] f[1] 1;for (int i 2; i n; i) {f[i] (f[i - 1] f[i - 2]) % mod;}return f[n];
}int main() {int n;scanf(%d,n);printf(%d,numWays(n));return 0;
}
(2) 爬楼梯问题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 int climbStairs(int n) {int f[46];f[0] f[1] 1;for(int i 2;in;i){f[i] f[i-1] f[i-2];}return f[n];
}
(3) 将数字变成0的操作方案 给你一个非负数num,请你返回将它变成0所需的步数如果当前数字是偶数你需要它除以2否则减去1. 非动态规划解法
int numberOfSteps(int num) {int n 0;while(num ! 0){if(num%2 0){num /2;n;}else{num -1;n;}} return n;
}
动态规划解法
int numberOfSteps(int num) {int f[1000001];for(int i 0;inum;i){if(i % 2 1){f[i] f[i-1] 1;}else{f[i] f[i/2] 1;}return f[num];}
}
(4)爬楼梯的最小成本 数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。 每当爬上一个阶梯都要花费对应的体力值一旦支付了相应的体力值就可以选择向上爬一个阶梯或者爬两个阶梯。 请找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。 int min(int a,int b){return ab?a:b;
}
int minCostClimbingStairs(int* cost, int costSize){int f[1024];f[0] f[1] 0;for(int i 2;icostSize;i){f[i] min(f[i-1]cost[i-1],f[i-2]cost[i-2]);} return f[costSize];
} [2] 状态转移
(1) 打家劫舍 一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 int max(int a,int b){return ab?a:b;
}int rob(int* nums, int numsSize){int f[numsSize1];f[0] nums[0];for(int i 1;inumsSize;i){if(i 1){f[1] max(nums[0],nums[1]);}else{f[i] max(f[i-1],f[i-2]nums[i]);} }return f[numsSize-1];
}
(2) 打家劫舍Ⅱ 一个专业的小偷计划偷窃一个环形街道上沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 int max(int a,int b){return ab?a:b;
}int rob(int* nums, int numsSize){int dp[numsSize1][numsSize1];if(numsSize 1){return nums[0];}else if(numsSize 2){return max(nums[0],nums[1]);}dp[0][0] 0;dp[0][1] nums[0];for(int i 1;i numsSize;i){for(int j 0;j2;j){if(i 1){if(j 0){ dp[i][j] nums[1];}else{dp[i][j] nums[0];}}else if(i numsSize-1 j 1){dp[i][j] dp[i-1][j];}else{ dp[i][j] max(dp[i-1][j],dp[i-2][j]nums[i]);}}
}return max(dp[numsSize-1][0],dp[numsSize-1][1]);
}
(3)解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 1 - A 2 - B ... 25 - Y 26 - Z 然而在 解码 已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中2 和 5 与 25。 例如11106 可以映射为 AAJF 将消息分组为 (1, 1, 10, 6)KJF 将消息分组为 (11, 10, 6)消息不能分组为 (1, 11, 06) 因为 06 不是一个合法编码只有 6 是合法的。 注意可能存在无法解码的字符串。 给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串返回 0。 题目数据保证答案肯定是一个 32 位 的整数。 int numDecodings(char* s) {int len strlen(s);if (len 0 || s[0] 0) return 0; int dp[len 1];dp[0] 1; dp[1] (s[0] 0) ? 0 : 1; for (int i 2; i len; i) {int oneDigit (s[i - 1] ! 0); int twoDigits (s[i - 2] 1 || (s[i - 2] 2 s[i - 1] 6)); dp[i] oneDigit * dp[i - 1]; if (twoDigits) {dp[i] dp[i - 2]; }}return dp[len];
}
4获取生成数组中的最大值 给你一个整数 n 。按下述规则生成一个长度为 n 1 的数组 nums nums[0] 0nums[1] 1当 2 2 * i n 时nums[2 * i] nums[i]当 2 2 * i 1 n 时nums[2 * i 1] nums[i] nums[i 1] 返回生成数组 nums 中的 最大 值。 示例 1 输入n 7
输出3
解释根据规则nums[0] 0nums[1] 1nums[(1 * 2) 2] nums[1] 1nums[(1 * 2) 1 3] nums[1] nums[2] 1 1 2nums[(2 * 2) 4] nums[2] 1nums[(2 * 2) 1 5] nums[2] nums[3] 1 2 3nums[(3 * 2) 6] nums[3] 2nums[(3 * 2) 1 7] nums[3] nums[4] 2 1 3
因此nums [0,1,1,2,1,3,2,3]最大值 3int getMaximumGenerated(int n) {int nums[110];nums[0] 0;nums[1] 1;for(int i 1;in;i){if(2*i 2 2*i n){nums[2*i] nums[i];}if(2 2*i1 2*i1 n){nums[2 * i 1] nums[i] nums[i 1];}}int v 0;for(int i 1;in;i){if(v nums[i]){v nums[i]; }}return v;
}
(5)分割数组以得到最大值 给你一个整数数组 arr请你将该数组分隔为长度 最多 为 k 的一些连续子数组。分隔完成后每个子数组的中的所有值都会变为该子数组中的最大值。 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。 示例 1 输入arr [1,15,7,9,2,5,10], k 3
输出84
解释数组变为 [15,15,15,9,10,10,10] 示例 2 输入arr [1,4,1,5,7,3,6,1,9,9,3], k 4
输出83示例 3 输入arr [1], k 1
输出1int max(int a,int b){return a b ? a : b;
}int maxSumAfterPartitioning(int* arr, int arrSize, int k) {int maxv,cnt;int dp[500];for(int i 0;i arrSize; i){maxv 0;dp[i] 0;cnt 0;for(int j i;j0;--j){if(arr[j] maxv){maxv arr[j];}cnt;if(cnt k){break;}if(j){dp[i] max(dp[i],dp[j-1] cnt*maxv);}else{dp[i] max(dp[i],cnt*maxv);}}}return dp[arrSize-1];
}
(6)单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 bool wordBreak(char* s, char** wordDict, int wordDictSize) {int dp[350];memset(dp,0,sizeof(dp));int i,j,k,l;int n strlen(s);for(i 0;in;i){for(j 0;jwordDictSize;j){l strlen(wordDict[j]);if(i-l1 0){ continue;}if(i-l ! -1 ! dp[i-l]){ continue;}for(k 0; kl ;k){if(s[i-l1k] ! wordDict[j][k]){break;}}if(k l){dp[i] 1;break;}} }return dp[i-1];
} [3] 前缀和
(1) 哪种连续子字符串更长 给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串返回 true 否则返回 false 。 例如s 110100010 中由 1 组成的最长连续子字符串的长度是 2 由 0 组成的最长连续子字符串的长度是 3 。 注意如果字符串中不存在 0 此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。 int max(int a,int b){return ab?a:b;
}bool checkZeroOnes(char* s) {int dp[2][101];int maxV[2];int n strlen(s);memset(dp,0,101);maxV[0] maxV[1] 0;maxV[s[0] - 0] 1;dp[s[0] - 0][0] 1;for(int i 1;in;i){if(s[i] s[i-1]){dp[s[i] - 0][i] dp[s[i] - 0][i-1] 1;}else{dp[s[i] - 0][i] 1;}maxV[0] max(maxV[0],dp[0][i]);maxV[1] max(maxV[1],dp[1][i]);}return maxV[1] maxV[0];}
2寻找数组中心下标 给你一个整数数组 nums 请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。 int pivotIndex(int* nums, int numsSize) {int sum [10001];for(int i 0;inumsSize;i){sum[i] nums[i];if(i){sum[i] sum[i-1];}}if(sum[numsSize - 1] sum[0]){return 0;}for(int i 1;inumsSize;i){if(sum[i] sum[numsSize-1] - sum[i -1]){return i;}}return -1;
}
3统计全为1的正方形子矩阵 给你一个 m * n 的矩阵矩阵中的元素不是 0 就是 1请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。 示例 1 输入matrix
[[0,1,1,1],[1,1,1,1],[0,1,1,1]
]
输出15
解释
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 10 4 1 15. #include stdio.h
#include stdlib.hint countSquares(int** matrix, int matrixSize, int* matrixColSize) {if (matrix NULL || matrixSize 0 || matrixColSize[0] 0) {return 0;}int m matrixSize;int n matrixColSize[0];int** dp (int**)malloc(m * sizeof(int*));for (int i 0; i m; i) {dp[i] (int*)malloc(n * sizeof(int));}int count 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 1) {if (i 0 || j 0) {dp[i][j] 1;} else {dp[i][j] (dp[i - 1][j] dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]);dp[i][j] (dp[i][j] dp[i - 1][j - 1] ? dp[i][j] : dp[i - 1][j - 1]) 1;}count dp[i][j];} else {dp[i][j] 0;}}}// 释放内存for (int i 0; i m; i) {free(dp[i]);}free(dp);return count;
} 2 二维DP
1粉刷房子 假如有一排房子共 n 个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如costs[0][0] 表示第 0 号房子粉刷成红色的成本花费costs[1][2] 表示第 1 号房子粉刷成绿色的花费以此类推。 请计算出粉刷完所有房子最少的花费成本。 int min(int a,int b){return ab?a:b;
}int minCost(int** costs, int costsSize, int* costsColSize){int m costsColSize[0];int n costsSize;int dp[101][3];for(int i 0;i3;i){dp[0][i] costs[0][i];}for(int i 1;in;i){for(int j 0; j3;j){dp[i][j] 1000000000;for(int k 0;k3;k){if(k ! j){dp[i][j] min(dp[i][j],dp[i-1][k] costs[i][j]);}}}}return min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
} 3 经典DP
[1] 最大子数组和 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组是数组中的一个连续部分。 int max(int a,int b){return ab?a:b;
}int maxSubArray(int* nums, int numsSize) {int dp[100001];int maxV nums[0];dp[0] nums[0];for(int i 1;inumsSize;i){dp[i] nums[i];if(dp[i-1] 0){dp[i] dp[i-1];}maxV max(maxV,dp[i]);}return maxV;} [2] 最长单调子序列 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列 。 示例 1 输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。 int max(int a,int b){return ab?a:b;
}int lengthOfLIS(int* nums, int numsSize) {int maxV 0;int dp[numsSize];for(int i 0;i numsSize; i){dp[i] 1;for(int j 0; j i; j){if(nums[j] nums[i]) {if(dp[j] 1 dp[i]){dp[i] dp[j] 1;}}}maxV max(maxV,dp[i]);}return maxV;} 还可以继续使用二分法优化
2最长递增子序列的个数 给定一个未排序的整数数组 nums 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。 示例 1: 输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 int findNumberOfLIS(int* nums, int numsSize){int maxlen0,ans0;//maxlen为最长递增子序列长度ans为其个数int dp[numsSize],cnt[numsSize];//dp[i]表示nums中以下标i结尾的最长递增子序列的长度//cnt[i]表示nums中以下标i结尾的最长递增子序列的个数for (int i 0; i numsSize; i) {dp[i] 1;cnt[i] 1;for (int j 0; j i; j) {if (nums[j]nums[i]) {if (dp[j] 1 dp[i]) {dp[i] dp[j] 1;cnt[i] cnt[j]; // dp[i]发生变化,cnt[i]重新计数} else if (dp[j] 1 dp[i]) {cnt[i] cnt[j];//有相同的dp[i]cnt[i]要再加上cnt[j]}}}if (dp[i] maxlen) {//先找到最长递增子序列再赋值其个数maxlen dp[i];ans cnt[i]; // 重置计数} else if (dp[i] maxlen) {//如果不同下标最长子序列长度相同再加上其个数ans cnt[i];}}return ans;
} 3最长等差数列 给你一个整数数组 nums返回 nums 中最长等差子序列的长度。 回想一下nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] 且 0 i1 i2 ... ik nums.length - 1。并且如果 seq[i1] - seq[i]( 0 i seq.length - 1) 的值都相同那么序列 seq 是等差的。 #define MIN(a, b) ((a) (b) ? (a) : (b))
#define MAX(a, b) ((a) (b) ? (a) : (b))int longestArithSeqLength(int* nums, int numsSize) {int maxVal nums[0];int minVal nums[0];for (int i 0; i numsSize; i) {maxVal MAX(maxVal, nums[i]);minVal MIN(minVal, nums[i]);}int diff maxVal - minVal;int ans 1;for (int d -diff; d diff; d) {int f[maxVal 1];memset(f, 0xff, sizeof(f));for (int i 0; i numsSize; i) {int prev nums[i] - d; if (prev minVal prev maxVal f[prev] ! -1) {f[nums[i]] MAX(f[nums[i]], f[prev] 1);ans MAX(ans, f[nums[i]]);}f[nums[i]] MAX(f[nums[i]], 1);}}return ans;
}//思路与算法// 我们可以使用动态规划的方法解决本题。// 记 f[i][d][num] 表示使用数组 nums 中下标小于等于 i 的元素构造公差为 d 的等差数列并且最后一个元素为 num 时等差数列长度的最大值。在进行状态转移时我们考虑是否将当前的第 i 个元素作为末项加入等差数列。// 如果不加入等差数列那么每一项的答案应该与使用下标小于等于 i−1 的元素对应的答案相同即// f[i][d][num]←f[i−1][d][num]
// 如果加入等差数列那么有两种情况。第一种是等差数列的长度至少为 2既然末项是 nums[i]那么倒数第二项就是 nums[i]−d这样我们就可以得到状态转移方程// f[i][d][nums[i]]←f[i−1][d][nums[i]−d]1
// 这里需要保证 nums[i]−d 落在满足要求的范围内即必须在数组 nums 中最小值和最大值之间。并且 f[i−1][d][nums[i]−d] 本身也需要是一个合法的状态即必须要存在以 nums[i]−d 为末项的等差数组。// 第二种是等差数列的长度为 1即 nums[i] 单独形成一个等差数组即// f[i][d][nums[i]]←1
// 由于我们需要求出的是最大值因此所有的状态转移都会取二者的较大值。如果我们使用数组表示 f可以将所有状态的初始值均设置为 −1表示不合法的状态如果我们使用哈希表表示 f那么没有在哈希表中出现过的状态就是不合法的状态。// 最终的答案即为 f[n−1][..][..] 中的最大值其中 n 是数组 nums 的长度。// 需要注意的是d 的取值范围是 [−diff,diff ]其中 diff 是数组 nums 中最大值与最小值的差。// 优化// 在上面的状态转移方程中我们发现当状态的第一维从 i−1 变成 i 后实际上只有 f[i][d][nums[i]] 可能会相较于 f[i−1][d][nums[i]] 的值发生变化而其余的值均保持不变。因此我们可以省去第一维在状态转移时只需要修改最多一个状态的值。// 此时状态变为 f[d][num]当我们遍历到数组 nums 的第 i 个元素时只需要进行// f[d][nums[i]]←f[d][nums[i]−d]1
// 以及// f[d][nums[i]]←1
// 这两个状态转移即可。进一步我们发现f[d][..] 只会从 f[d][..] 转移而来因此我们可以继续省去当前的第一维使用一个外层循环枚举 d而在内层循环中只需要进行// f[nums[i]]←f[nums[i]−d]1(1)
// 以及// f[nums[i]]←1
// 这两个状态转移即可。// 显然最终的答案至少为 1。因此我们只需要在进行 (1) 的状态转移时使用 f[nums[i]] 对答案进行更新。// 作者力扣官方题解
// 链接https://leetcode.cn/problems/longest-arithmetic-subsequence/solutions/2238031/zui-chang-deng-chai-shu-lie-by-leetcode-eieq8/
// 来源力扣LeetCode
// 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
4最长斐波那契数列 如果序列 X_1, X_2, ..., X_n 满足下列条件就说它是 斐波那契式 的 n 3对于所有 i 2 n都有 X_i X_{i1} X_{i2} 给定一个严格递增的正整数数组形成序列 arr 找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在返回 0 。 回想一下子序列是从原序列 arr 中派生出来的它从 arr 中删掉任意数量的元素也可以不删而不改变其余元素的顺序。例如 [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列 示例 1 输入: arr [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。 //1
typedef struct {int key;int val;UT_hash_handle hh;
} HashItem;#define MAX(a, b) ((a) (b) ? (a) : (b))int lenLongestFibSubseq(int* arr, int arrSize){HashItem *indices NULL, *pEntry NULL;for (int i 0; i arrSize; i) {pEntry (HashItem *)malloc(sizeof(HashItem));pEntry-key arr[i];pEntry-val i;HASH_ADD_INT(indices, key, pEntry);}int **dp (int **)malloc(sizeof(int *) * arrSize);int ans 0;for (int i 0; i arrSize; i) {dp[i] (int *)malloc(sizeof(int) * arrSize);memset(dp[i], 0, sizeof(int) * arrSize);}for (int i 0; i arrSize; i) {for (int j i - 1; j 0 arr[j] * 2 arr[i]; j--) {int k -1;int target arr[i] - arr[j];pEntry NULL;HASH_FIND_INT(indices, target, pEntry);if (pEntry) {k pEntry-val;}if (k 0) {dp[j][i] MAX(dp[k][j] 1, 3);}ans MAX(ans, dp[j][i]);}}for (int i 0; i arrSize; i) {free(dp[i]);}free(dp);HashItem *curr NULL, *tmp NULL;HASH_ITER(hh, indices, curr, tmp) {HASH_DEL(indices, curr); free(curr); }return ans;
}
// (2)int findV(int *arr,int min,int max,int var){int idx 0;while(min max){int mid (minmax)/2;if(var arr[mid]){min mid 1;}else if(var arr[mid]){max mid - 1;}else{return mid;}}return -1;
}int max(int a,int b){return ab?a:b;}int lenLongestFibSubseq(int* arr, int arrSize){int ans 0;int dp[1001][1001];for(int i 0;iarrSize;i){for(int j i1;jarrSize;j){int idx findV(arr,0,i-1,arr[j]-arr[i]);if(idx ! -1){dp[i][j] dp[idx][i] 1;}else{dp[i][j] 2;}ans max(ans,dp[i][j]);}}return ans3?ans:0;}
[3] 最长公共子序列
1最长公共子序列 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。 一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。 例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 int max(int a,int b){return ab?a:b;}int longestCommonSubsequence(char * text1, char * text2){int ans 0;int dp[1001][1001];int n strlen(text1);int m strlen(text2);for(int i 0;in;i){for(int j 0;jm;j){int same (text1[i] text2[j]?1:0);if(i 0 j 0){dp[i][j] same;}else if(i 0){dp[i][j] dp[i][j-1] || same;}else if(j 0){dp[i][j] dp[i-1][j] || same;}else if(same){dp[i][j] dp[i-1][j-1] 1; }else{dp[i][j] max(dp[i-1][j],dp[i][j-1]);}}}return dp[n-1][m-1];
}
2最长回文子序列 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。 一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。 例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 int max(int a,int b){return ab?a:b;}int longestCommonSubsequence(char * text1, char * text2){int ans 0;int dp[1001][1001];int n strlen(text1);int m strlen(text2);for(int i 0;in;i){for(int j 0;jm;j){int same (text1[i] text2[j]?1:0);if(i 0 j 0){dp[i][j] same;}else if(i 0){dp[i][j] dp[i][j-1] || same;}else if(j 0){dp[i][j] dp[i-1][j] || same;}else if(same){dp[i][j] dp[i-1][j-1] 1; }else{dp[i][j] max(dp[i-1][j],dp[i][j-1]);}}}return dp[n-1][m-1];
}
[4] 最短编辑距离
1编辑距离 困难 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符删除一个字符替换一个字符 class Solution {
public:int minDistance(string word1, string word2) {int n word1.length();int m word2.length();// 有一个字符串为空串if (n * m 0) return n m;// DP 数组vectorvectorint D(n 1, vectorint(m 1));// 边界状态初始化for (int i 0; i n 1; i) {D[i][0] i;}for (int j 0; j m 1; j) {D[0][j] j;}// 计算所有 DP 值for (int i 1; i n 1; i) {for (int j 1; j m 1; j) {int left D[i - 1][j] 1;int down D[i][j - 1] 1;int left_down D[i - 1][j - 1];if (word1[i - 1] ! word2[j - 1]) left_down 1;D[i][j] min(left, min(down, left_down));}}return D[n][m];}
};
[5] 杨辉三角
1杨辉三角 给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中每个数是它左上方和右上方的数的和。 int** generate(int numRows, int* returnSize, int** returnColumnSizes) {// 设置返回的行数*returnSize numRows;// 分配存储每行列数的数组*returnColumnSizes (int*)malloc(numRows * sizeof(int));// 分配存储杨辉三角的二维数组int** triangle (int**)malloc(numRows * sizeof(int*));for (int i 0; i numRows; i) {// 设置当前行的列数(*returnColumnSizes)[i] i 1;// 为当前行分配内存triangle[i] (int*)malloc((i 1) * sizeof(int));for (int j 0; j i; j) {if (j 0 || j i) {// 每行的第一个和最后一个元素为 1triangle[i][j] 1;} else {// 其他元素为上一行相邻两个元素之和triangle[i][j] triangle[i - 1][j] triangle[i - 1][j - 1];}}}return triangle;
}
2不同路径 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径 示例 1 输入m 3, n 7
输出28 旋转45度 就得到一个杨辉三角
int uniquePaths(int m, int n){int ans 0;int dp[1024][1024];for(int i 1;i m;i ){for(int j 1;j n;j){if(j 1 || j 1){dp[i][j] 1;}else{dp[i][j] dp[i][j-1] dp[i-1][j];}}}return dp[m][n];
}
3珠宝的最高价值 现有一个记作二维矩阵 frame 的珠宝架其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为 只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下角时停止拿取 注意珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝比如 frame [[0]]。 示例 1 输入frame [[1,3,1],[1,5,1],[4,2,1]]
输出12
解释路径 1→3→5→2→1 可以拿到最高价值的珠宝int max(int a,int b){return ab?a:b;
}int jewelleryValue(int** frame, int frameSize, int* frameColSize) {int dp[201][201];for(int i 0;i frameSize;i){for(int j 0;j frameColSize[i];j ){if(i 0 j 0){dp[i][j] frame[0][0];}else if(i 0){dp[i][j] frame[i][j] dp[i][j-1];}else if(j 0){dp[i][j] frame[i][j] dp[i-1][j];}else{dp[i][j] frame[i][j] max(dp[i-1][j],dp[i][j-1]);}}}return dp[frameSize - 1][frameColSize[frameSize - 1] - 1];}
4最小路径之和 给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明一个机器人每次只能向下或者向右移动一步。 示例 1 输入grid [[1,3,1],[1,5,1],[4,2,1]]
输出7
解释因为路径 1→3→1→1→1 的总和最小。 int min(int a,int b){return ab?a:b;
}int minPathSum(int** grid, int gridSize, int* gridColSize){int dp[201][201];for(int i 0;i gridSize;i){for(int j 0;j gridColSize[i];j ){if(i 0 j 0){dp[i][j] grid[0][0];}else if(i 0){dp[i][j] grid[i][j] dp[i][j-1];}else if(j 0){dp[i][j] grid[i][j] dp[i-1][j];}else{dp[i][j] grid[i][j] min(dp[i-1][j],dp[i][j-1]);}}}return dp[gridSize - 1][gridColSize[gridSize - 1] - 1];}
[6] 经典股票问题
1买卖股票的最佳时机 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 示例 1 输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。 int min(int a,int b){return ab?a:b;
}int max(int a,int b){return ab?a:b;
}int maxProfit(int* prices, int pricesSize) {int* dp (int *)malloc(sizeof(int) * pricesSize);int maxV 0;for(int i 0;i pricesSize;i){if(i 0){dp[i] prices[0];}else{dp[i] min(prices[i],dp[i-1]);}maxV max(maxV,(prices[i] - dp[i]));}return maxV;
} 2买卖股票的最佳时机Ⅱ 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1 输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。
最大总利润为 4 3 7 。 int max(int a,int b){return ab?a:b;
}int maxProfit(int* prices, int pricesSize) {int maxM 10000000;int minM -10000000;int dp[pricesSize][4];// dp[i][0] 未买入// dp[i][1] 买入// dp[i][2] 持有中// dp[i][3] 卖出for(int i 0;i pricesSize; i){if(i 0){dp[i][0] 0;dp[i][1] -prices[i];dp[i][2] minM;dp[i][3] minM;}else{dp[i][0] max(dp[i-1][3],dp[i-1][0]);dp[i][1] max(dp[i-1][3],dp[i-1][0]) - prices[i];dp[i][2] max(dp[i-1][2],dp[i-1][1]);dp[i][3] max(dp[i-1][1],dp[i-1][2]) prices[i];}}return max(dp[pricesSize-1][0],max(dp[pricesSize -1][1],max(dp[pricesSize-1][2],dp[pricesSize-1][3])));} 3买卖股票的最佳时机Ⅲ 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1: 输入prices [3,3,5,0,0,3,1,4]
输出6
解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。#define max(a, b) ((a) (b) ? (b) : (a))int maxProfit(int* prices, int pricesSize) {int buy1 -prices[0], sell1 0;int buy2 -prices[0], sell2 0;for (int i 1; i pricesSize; i) {buy1 max(buy1, -prices[i]);sell1 max(sell1, buy1 prices[i]);buy2 max(buy2, sell1 - prices[i]);sell2 max(sell2, buy2 prices[i]);}return sell2;
} 4买卖股票的最佳时机Ⅳ 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1 输入k 2, prices [2,4,1]
输出2
解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。 int maxProfit(int k, int* prices, int pricesSize) {int n pricesSize;if (n 0) {return 0;}k fmin(k, n / 2);int buy[n][k 1], sell[n][k 1];memset(buy, 0, sizeof(buy));memset(sell, 0, sizeof(sell));buy[0][0] -prices[0];sell[0][0] 0;for (int i 1; i k; i) {buy[0][i] sell[0][i] INT_MIN / 2;}for (int i 1; i n; i) {buy[i][0] fmax(buy[i - 1][0], sell[i - 1][0] - prices[i]);for (int j 1; j k; j) {buy[i][j] fmax(buy[i - 1][j], sell[i - 1][j] - prices[i]);sell[i][j] fmax(sell[i - 1][j], buy[i - 1][j - 1] prices[i]);}}int ret 0;for (int i 0; i k; i) {ret fmax(ret, sell[n - 1][i]);}return ret;
} 4 背包DP
[1] 零一背包
1分割等和子集 给定一个非空的正整数数组 nums 请判断能否将这些数字分成元素和相等的两部分。 示例 1 输入nums [1,5,11,5]
输出true
解释nums 可以分割成 [1, 5, 5] 和 [11] 。 bool canPartition(int* nums, int numsSize){int sum 0;int dp[200001];for(int i 0;inumsSize;i){sum nums[i];}memset(dp,0,sizeof(dp));if(sum 1){return false;}sum / 2;dp[0] 1;for(int i 0;inumsSize;i){for(int j sum;j nums[i];j--){dp[j] | dp[j - nums[i]];}if(dp[sum]) return true;}return false;
}
[2] 完全背包
1最少的硬币数量 给定不同面额的硬币 coins 和一个总金额 amount 。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。 class Solution {//define maxn 10010//define inf 10000000int dp[maxn];
public:int coinChange(vectorint coins, int amount) {int i, j;for(i 0; i amount; i) {dp[i] inf;}dp[0] 0;for(i 0; i coins.size(); i) {for(j coins[i]; j amount; j) {if( dp[j-coins[i]] 1 dp[j]) {dp[j] dp[j-coins[i]] 1;}}}if(dp[amount] inf) dp[amount] -1;return dp[amount];}
}; 5 记忆化搜索
1最长递增路径 给定一个 m x n 整数矩阵 matrix 找出其中 最长递增路径 的长度。 对于每个单元格你可以往上下左右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外即不允许环绕。 示例 1 输入matrix [[9,9,4],[6,6,8],[2,1,1]]
输出4
解释最长递增路径为 [1, 2, 6, 9]。 int max(int a,int b){return ab?a:b;
}int dir[4][2] {{0,1},{0,-1},{1,0},{-1.,0}};int dfs(int dp[2010][2010],int** matrix, int matrixSize, int* matrixColSize,int x,int y){int tx,ty;if(dp[x][y] ! -1){return dp[x][y];}dp[x][y] 1;for(int i 0;i 4;i){tx x dir[i][1];ty y dir[i][0];if(tx 0 || ty 0 || tx matrixSize || ty matrixColSize[tx]){continue;}if(matrix[tx][ty] matrix[x][y]){continue;}dp[x][y] max(dp[x][y],dfs(dp,matrix,matrixSize,matrixColSize,tx,ty)1);}return dp[x][y];}int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize){int length 1;int dp[2010][2010];memset(dp,-1,sizeof(dp));for(int i 0;imatrixSize;i){for(int j 0;jmatrixColSize[i];j){length max(length,dfs(dp,matrix,matrixSize,matrixColSize,i,j));}}return length;
} 学习时间 2025.2.2
关于动态规划学习 这份笔记并不完善 还有部分题型没有分类学习 后续有涉及再继续补充 文章转载自： http://www.morning.ghlyy.cn.gov.cn.ghlyy.cn http://www.morning.qsdnt.cn.gov.cn.qsdnt.cn http://www.morning.nnmnz.cn.gov.cn.nnmnz.cn http://www.morning.qbfqb.cn.gov.cn.qbfqb.cn http://www.morning.ai-wang.cn.gov.cn.ai-wang.cn http://www.morning.bzcjx.cn.gov.cn.bzcjx.cn http://www.morning.hlfnh.cn.gov.cn.hlfnh.cn http://www.morning.rmtmk.cn.gov.cn.rmtmk.cn http://www.morning.btpll.cn.gov.cn.btpll.cn http://www.morning.ktnt.cn.gov.cn.ktnt.cn http://www.morning.llgpk.cn.gov.cn.llgpk.cn http://www.morning.ftzll.cn.gov.cn.ftzll.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.qfplp.cn.gov.cn.qfplp.cn http://www.morning.dshkp.cn.gov.cn.dshkp.cn http://www.morning.hmbtb.cn.gov.cn.hmbtb.cn http://www.morning.rhqr.cn.gov.cn.rhqr.cn http://www.morning.sjwws.cn.gov.cn.sjwws.cn http://www.morning.lmfxq.cn.gov.cn.lmfxq.cn http://www.morning.rqsnl.cn.gov.cn.rqsnl.cn http://www.morning.hxrg.cn.gov.cn.hxrg.cn http://www.morning.htfnz.cn.gov.cn.htfnz.cn http://www.morning.jcbjy.cn.gov.cn.jcbjy.cn http://www.morning.kllzy.com.gov.cn.kllzy.com http://www.morning.kqcqr.cn.gov.cn.kqcqr.cn http://www.morning.bnfjh.cn.gov.cn.bnfjh.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.tnktt.cn.gov.cn.tnktt.cn http://www.morning.jczjf.cn.gov.cn.jczjf.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.wqkfm.cn.gov.cn.wqkfm.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.jhfkr.cn.gov.cn.jhfkr.cn http://www.morning.hbywj.cn.gov.cn.hbywj.cn http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.dbnrl.cn.gov.cn.dbnrl.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.rnjgh.cn.gov.cn.rnjgh.cn http://www.morning.kszkm.cn.gov.cn.kszkm.cn http://www.morning.zmzdx.cn.gov.cn.zmzdx.cn http://www.morning.webpapua.com.gov.cn.webpapua.com http://www.morning.dmcxh.cn.gov.cn.dmcxh.cn http://www.morning.rgsgk.cn.gov.cn.rgsgk.cn http://www.morning.gpnwq.cn.gov.cn.gpnwq.cn http://www.morning.sqgqh.cn.gov.cn.sqgqh.cn http://www.morning.kjdxh.cn.gov.cn.kjdxh.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn http://www.morning.kdlzz.cn.gov.cn.kdlzz.cn http://www.morning.jcjgh.cn.gov.cn.jcjgh.cn http://www.morning.pwfwk.cn.gov.cn.pwfwk.cn http://www.morning.hmmnb.cn.gov.cn.hmmnb.cn http://www.morning.rszbj.cn.gov.cn.rszbj.cn http://www.morning.qnzgr.cn.gov.cn.qnzgr.cn http://www.morning.cwnqd.cn.gov.cn.cwnqd.cn http://www.morning.bdypl.cn.gov.cn.bdypl.cn http://www.morning.nzlqt.cn.gov.cn.nzlqt.cn http://www.morning.jjnry.cn.gov.cn.jjnry.cn http://www.morning.rnrfs.cn.gov.cn.rnrfs.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.ryysc.cn.gov.cn.ryysc.cn http://www.morning.tlrxt.cn.gov.cn.tlrxt.cn http://www.morning.gtkyr.cn.gov.cn.gtkyr.cn http://www.morning.flmxl.cn.gov.cn.flmxl.cn http://www.morning.rjxwq.cn.gov.cn.rjxwq.cn http://www.morning.mxnhq.cn.gov.cn.mxnhq.cn http://www.morning.rgwz.cn.gov.cn.rgwz.cn http://www.morning.rongxiaoman.com.gov.cn.rongxiaoman.com http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.dtfgr.cn.gov.cn.dtfgr.cn http://www.morning.pcshb.cn.gov.cn.pcshb.cn http://www.morning.kybjr.cn.gov.cn.kybjr.cn http://www.morning.thrcj.cn.gov.cn.thrcj.cn http://www.morning.qfnrx.cn.gov.cn.qfnrx.cn http://www.morning.xmjzn.cn.gov.cn.xmjzn.cn http://www.morning.lcjw.cn.gov.cn.lcjw.cn http://www.morning.pwbps.cn.gov.cn.pwbps.cn http://www.morning.mlntx.cn.gov.cn.mlntx.cn http://www.morning.tlbdy.cn.gov.cn.tlbdy.cn http://www.morning.yzygj.cn.gov.cn.yzygj.cn
