苏州市吴江区住房和城乡建设局网站竞价在什么网站上做

当前位置： 首页 > news >正文

苏州市吴江区住房和城乡建设局网站,竞价在什么网站上做,最近的男科医院是哪家医院,茅台酒网站建设方案动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心#xff0c;贪心没有状态推… 动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的例如有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。 状态转移公式递推公式是很重要但动规不仅仅只有递推公式。对于动态规划问题我将拆解为如下五步曲这五步都搞清楚了才能说把动态规划真的掌握了 确定 dp 数组dp table以及下标的含义确定递推公式dp 数组如何初始化确定遍历顺序举例推导 dp 数组 因为一些情况是递推公式决定了dp数组要如何初始化写动规题目代码出问题很正常找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的一些同学对于dp的学习是黑盒的状态就是不清楚dp数组的含义不懂为什么这么初始化递推公式背下来了遍历顺序靠习惯就是这么写的然后一鼓作气写出代码如果代码能通过万事大吉通过不了的话就凭感觉改一改。
题目斐波那契数 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 class Solution { public:int fib(int n) {if(n2){return n;}int resfib(n-1)fib(n-2);return res;} };时间复杂度O(2^n)空间复杂度O(n)算上了编程语言中实现递归的系统栈所占空间 动态规划这里我们要用一个一维 dp 数组来保存递归的结果确定dp数组以及下标的含义dp[i]的定义为第i个数的斐波那契数值是dp[i] 确定递推公式状态转移方程 dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化dp[0] 0; dp[1] 1;确定遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 class Solution { public:int fib(int n) {if(n2){return n;}vectorint dp(n1,0);dp[1]1;for(int i2;idp.size();i){dp[i]dp[i-1]dp[i-2];}return dp[dp.size()-1];} };时间复杂度O(n); 空间复杂度O(n) if(n2){return n;}int dp[2]{0,1};for(int i2;in1;i){dp[i%2]dp[0]dp[1];}return dp[(n)%2];时间复杂度O(n);空间复杂度O(1)
题目爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 爬到第一层楼梯有一种方法爬到二层楼梯有两种方法。那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。此时大家应该发现了这不就是斐波那契数列么 class Solution { public:int climbStairs(int n) {if(n3){return n;}int dp[2]{1,2};for(int i2;in;i){dp[i%2]dp[0]dp[1];}return dp[(n-1)%2];} };后面将讲解的很多动规的题目其实都是当前状态依赖前两个或者前三个状态都可以做空间上的优化但我个人认为面试中能写出版本一就够了哈清晰明了如果面试官要求进一步优化空间的话我们再去优化。
题目使用最小花费爬楼梯 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。 确定dp数组以及下标的含义本题只需要一个一维数组dp[i]就可以了。dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。确定递推公式可以有两个途径得到dp[i]一个是dp[i-1] 一个是dp[i-2]。dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1]。dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] cost[i - 2]。一定是选最小的所以dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);dp数组如何初始化看一下递归公式dp[i]由dp[i - 1]dp[i - 2]推出既然初始化所有的dp[i]是不可能的那么只初始化dp[0]和dp[1]就够了其他的最终都是dp[0]dp[1]推出。题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的但从 第0 个台阶 往上跳的话需要花费 cost[0]。所以初始化 dp[0] 0dp[1] 0; class Solution { public:int minCostClimbingStairs(vectorint cost) {if(cost.size()3){return min(cost[0],cost[1]);}vectorint dp(cost.size()1,0);for(int i2;idp.size();i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[cost.size()];} };题目不同路径 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径 这道题目刚一看最直观的想法就是用图论里的深搜来枚举出来有多少种路径。注意题目中说机器人每次只能向下或者向右移动一步那么其实机器人走过的路径可以抽象为一棵二叉树而叶子节点就是终点 class Solution { public:int track(int i,int j,int m,int n){if(im||jn){return 0;}if(im jn){return 1;}return track(i1,j,m,n)track(i,j1,m,n);}int uniquePaths(int m, int n) {return track(0,0,m-1,n-1);} };//超时那二叉树的节点个数就是 2^(m n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树其实没有遍历整个满二叉树只是近似而已深搜代码的时间复杂度为O(2^(m n - 1) - 1)可以看出这是指数级别的时间复杂度是非常大的。 动态规划机器人从(0 , 0) 位置出发到(m - 1, n - 1)终点。 确定dp数组dp table以及下标的含义dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。确定递推公式想要求dp[i ][ j]只能有两个方向来推导出来即dp[i - 1] [j] 和 dp[i] [j - 1]。那么很自然dp[i][j] dp[i - 1] [j] dp[i] [j - 1]因为dp[i][j]只有这两个方向过来。dp数组的初始化:首先dp[i] [0]一定都是1因为从(0, 0)的位置到(i, 0)的路径只有一条那么dp[0] [j]也同理。确定遍历顺序:dp[i] [j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。 class Solution { public:int uniquePaths(int m, int n) {vectorvectorint dp(m,vectorint(n,1));for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];} };时间复杂度O(m × n)空间复杂度O(m × n) 一共mn的话无论怎么走走到终点都需要 m n - 2 步。在这m n - 2 步中一定有 m - 1 步是要向下走的不用管什么时候向下走。可以转化为给你m n - 2个不同的数随便取m - 1个数有几种取法。那么这就是一个组合问题了。求组合的时候要防止两个int相乘溢出 所以不能把算式的分子分母都算出来再做除法。需要在计算分子的时候不断除以分母代码如下 class Solution { public:int uniquePaths(int m, int n) {long long son1;int momm-1;int countm-1;int tmn-2;while(count–){son * t–;while(mom!0 son%mom0){son / mom; mom–;}}return son;} };题目不同路径 II 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。 数论解决完全不行不止一块障碍物 class Solution { public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int flag 0;int temp_m0,temp_n0;for(int i0;iobstacleGrid.size();i){for(int j0;jobstacleGrid[0].size();j){if(obstacleGrid[i][j]){temp_mi;temp_nj;flag1;break;}}}int count_sumobstacleGrid.size()-1;long long son_sum1;int mom_sumobstacleGrid.size()-1;int mnobstacleGrid.size()obstacleGrid[0].size()-2;while(count_sum–){son_sum * mn–;while(mom_sum!0 son_sum%mom_sum0){son_sum / mom_sum;mom_sum–;}}if(flag0){return son_sum;}long long son11;int mom1 temp_m;int count temp_m;int mn1 temp_mtemp_n;while(count–){son1 * mn1–;while(mom1!0 son1%mom10){son1 / mom1;mom1–;}}long long son21;int mom2 obstacleGrid.size()-temp_m-1;int count2 obstacleGrid.size()-temp_m-1;int mn2 obstacleGrid.size()-temp_mobstacleGrid[0].size()-temp_n-2;while(count2–){son2 * mn2–;while(mom2!0 son2%mom20){son2 / mom2;mom2–;}}return son_sum-son1*son2;} };//动态规划确定dp数组dp table以及下标的含义,dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。 确定递推公式dp[i][j] dp[i - 1] [j] dp[i] [j - 1]。因为有了障碍(i, j)如果就是障碍的话应该就保持初始状态初始状态为0。 dp数组如何初始化从(0, 0)的位置到(i, 0)的路径只有一条所以dp[i] [0]一定为1dp[0] [j]也同理。但如果(i, 0) 这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的dp[i] [ 0]应该还是初始值0。 class Solution { public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int mobstacleGrid.size();int nobstacleGrid[0].size();if(obstacleGrid[m-1][n-1]1 || obstacleGrid[0][0]1){return 0;}vectorvectorint dp(m,vectorint(n,0));for(int i0;imobstacleGrid[i][0]0;i){dp[i][0]1;}for(int i0;inobstacleGrid[0][i]0;i){dp[0][i]1;}for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]1){continue;}dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];} };时间复杂度O(n × m)n、m 分别为obstacleGrid 长度和宽度空间复杂度O(n × m)
题目整数拆分 给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。 确定dp数组dp table以及下标的含义dp[i]分拆数字 i可以得到的最大乘积为dp[i]。dp[i]的定义将贯彻整个解题过程下面哪一步想不懂了就想想dp[i]究竟表示的是啥 确定递推公式其实可以从1遍历j然后有两种渠道得到dp[i].一个是j * (i - j) 直接相乘。一个是j * dp[i - j]相当于是拆分(i - j)对这个拆分不理解的话可以回想dp数组的定义。j是从1开始遍历拆分j的情况在遍历j的过程中其实都计算过了。那么从1遍历j比较(i - j) * j和dp[i - j] * j 取最大的。递推公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));也可以这么理解j * (i - j) 是单纯的把整数拆分为两个数相乘而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。所以递推公式dp[i] max({dp[i], (i - j) * j, dp[i - j] * j}); dp的初始化这里我只初始化dp[2] 1从dp[i]的定义来说拆分数字2得到的最大乘积是1 class Solution { public:int integerBreak(int n) {vectorint dp(n1);dp[2]1;for(int i3;in;i){for(int j1;ji/2;j){dp[i]max(dp[i],max((i-j)*j,dp[i-j]*j));}}return dp[n];} };时间复杂度O(n^2); 空间复杂度O(n)
题目不同的二叉搜索树 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 n为1的时候有一棵树n为2有两棵树来看看n为3的时候 元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量 确定dp数组dp table以及下标的含义dp[i] 1到i为节点组成的二叉搜索树的个数为dp[i]。也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] 都是一样的。 确定递推公式dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]j相当于是头结点的元素从1遍历到i为止。所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量 dp数组如何初始化从定义上来讲空节点也是一棵二叉树也是一棵二叉搜索树这是可以说得通的。从递归公式上来讲dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0也需要dp[以j为头结点左子树节点数量] 1 否则乘法的结果就都变成0了。 class Solution { public:int numTrees(int n) {vectorint dp(n1);dp[0]1;for(int i1;in;i){for(int j1;ji;j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];} };时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( n ) O(n) O(n)