会计学堂 会计问答 问答详情还没有符合您的答案？立即在线咨询老师 免费咨询老师精选问题请问老师，小规模纳税人申报咨询服务费的时候，提示 问 没有销售不动产，不用填写 答老板把房子租给公司，老板个人要不要开票 问 最好有发票没有发票的话，你们单位没法抵扣所得税 答老师，研发费用加计扣除一般是怎么加计的？ 问 研发支出里面的费用化的这一部分可以加计扣除，
1.人员人工费用。
直接从事研发活动人员的工资薪金、基本养老保险费、基本医疗保险费、失业保险费、工伤保险费、生育保险费和住房公积金，以及外聘研发人员的劳务费用。
2.直接投入费用。
(1)研发活动直接消耗的材料、燃料和动力费用。
(2)用于中间试验和产品试制的模具、工艺装备开发及制造费，不构成固定资产的样品、样机及一般测试手段购置费，试制产品的检验费。
(3)用于研发活动的仪器、设备的运行维护、调整、检验、维修等费用，以及通过经营租赁方式租入的用于研发活动的仪器、设备租赁费。
3.折旧费用。
用于研发活动的仪器、设备的折旧费。
4.无形资产摊销。
用于研发活动的软件、专利权、非专利技术(包括许可证、专有技术、设计和计算方法等)的摊销费用。
5.新产品设计费、新工艺规程制定费、新药研制的临床试验费、勘探开发技术的现场试验费。
6.其他相关费用。
与研发活动直接相关的其他费用，如技术图书资料费、资料翻译费、专家咨询费、高新科技研发保险费，研发成果的检索、分析、评议、论证、鉴定、评审、评估、验收费用，知识产权的申请费、注册费、代理费，差旅费、会议费等。此项费用总额不得超过可加计扣除研发费用总额的10%.7.财政部和国家税务总局规定的其他费用。 答老师，有没有公司成立电子税务局和自然人系统操作 问 您好，自然人扣除客户端系统要到税务局网站下载的就是你们当地电子税务局的网站，每个地方不一样的 答你好，公司购买汽油，柴油，需要交印花税吗 问 你好，公司购买汽油和柴油，是需要交印花税的 答获取全部相关问题信息
亲爱的学员你好，我是来自
会计学堂的老师，很高兴为你服务，请问有什么可以帮助你的吗？
微信扫码加老师在线提问解答已经收到您的问题，请填写手机号，解答成功后可以快速查看答案。您正在与金牌答疑老师聊天请完成实名认证
应网络实名制要求，完成实名认证后才可以发表文章视频等内容，以保护账号安全。
(点击去认证)

文章目录前言一、基础篇动态规划1.1斐波那契数1.2爬楼梯1.3使用最小花费爬楼梯1.4不同路径1.5不同路径 II1.6整数拆分 【基础题中算比较有难度的】1.7不同的二叉搜索树 【基础题中算比较有难度的】 ※二、背包问题系列2.1 01背包系列2.1.1分割等和子集 【背包能不能装满】2.1.2最后一块石头的重量
【背包最多能装多少】2.1.3 目标和【装满背包有多少种方法】2.1.4 一和零【装满这个背包最多有多少个物品】2.2 完全背包系列2.2.1零钱兑换
【组合数】2.2.2组合总和Ⅳ【组合数】2.2.3爬楼梯（完全背包解法）【排列数】2.2.4零钱兑换【装满背包的最少物品】2.2.5完全平方数【装满背包的最少物品】2.2.6单词拆分【物品能不能把背包装满】※三、打家劫舍系列3.1打家劫舍3.2打家劫舍
【成环】3.3打家劫舍
【树状】四、股票系列4.1买卖股票的最佳时机【只能买卖一次】4.2买卖股票的最佳时机
【可以买卖多次】4.3买卖股票的最佳时机
【最多买卖2次】4.4买卖股票的最佳时机IV 【最多买卖k次】4.5最佳买卖股票时机含冷冻期 【买卖多次，卖出后有一天是冷冻期】4.6买卖股票的最佳时机含手续费【买卖多次，每次都有手续费】五、子序列问题5.1子序列（不连续）5.1.1最长上升子序列 ※5.1.2最长公共子序列5.1.3不相交的线【与5.1.2最长公共子序列几乎一样】5.2子序列（连续）5.2.1最长连续递增序列5.2.2最长重复子数组5.2.3最大子序和 ※5.3编辑距离5.3.1判断子序列【不连续】5.3.2不同的子序列 【不连续----hard】※5.3.3两个字符串的删除操作5.3.4编辑距离5.4回文5.4.1回文子串【连续】5.4.2最长回文子序列【不连续】前言动态规划五部曲：1、确定dp数组（dp table）以及下标的含义2、确定递推公式3、dp数组如何初始化4、确定遍历顺序5、举例推导dp数组一、基础篇动态规划1.1斐波那契数 1、确定dp数组以及下标的含义dp[i]：表示第i个斐波那契数值为dp[i]2、确定递推公式dp[i] = dp[i-1] + dp[i-2];3、dp数组如何初始化dp[0] = 1;dp[1] = 1;
1.2爬楼梯每次可以爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶n呢？ 1、确定dp数组以及下标的含义dp[i]：表示爬到第i个楼梯有dp[i]种方法2、确定递推公式dp[i] = dp[i-1] + dp[i-2];3、dp数组如何初始化dp[0] = 1;dp[1] = 1;
1.3使用最小花费爬楼梯每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。找出达到楼层顶部的最低花费。 1、确定dp数组以及下标的含义dp[i]：表示爬到第i个楼梯需要的最小花费为dp[i]2、确定递推公式dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);3、dp数组如何初始化dp[0] = 0，dp[1] = 0;
1.4不同路径机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？ 1、确定dp数组以及下标的含义dp[i][j]：表示走到i行j列时，有dp[i][j]中方法2、确定递推公式dp[i][j] = dp[i - 1][j] + dp[i][j-1] 【只能从两个方向过来】3、dp数组如何初始化dp[0][j] = 1dp[i][0] = 1;
1.5不同路径 II不同路径还不够，要有障碍。 1、确定dp数组以及下标的含义dp[i][j]：表示走到i行j列时，有dp[i][j]中方法2、确定递推公式多了一个前提条件就是：if( obstacleGrid[i][j] != 1 )dp[i][j] = dp[i - 1][j] + dp[i][j-1]else dp[i][j] = 03、dp数组如何初始化 【需要考虑障碍物】for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
1.6整数拆分 【基础题中算比较有难度的】给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回可以获得的最大乘积。 1、确定dp数组以及下标的含义dp[i]：表示整数i可以获得的最大乘积为dp[i]2、确定递推公式dp[i] = max(dp[i], dp[i-j]*j , (i-j)*j); j * (i - j) 是单纯的把整数拆分为两个数相乘j * dp[i - j]是拆分成两个以及两个以上的个数相乘
for(int i=3;i<=n;i++){for(int j = 1;j<i; j++){dp[i] = Math.max(dp[i], dp[i-j]*j, (i-j)*j);}
}
3、dp数组如何初始化dp[0] = 0;dp[1] = 0;dp[2] = 1;
1.7不同的二叉搜索树 【基础题中算比较有难度的】 ※给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量有2个元素的搜索树数量就是dp[2]。有1个元素的搜索树数量就是dp[1]。有0个元素的搜索树数量就是dp[0]。 1、确定dp数组以及下标的含义dp[i]：表示i个节点可以组成dp[i]棵二叉搜索树2、确定递推公式dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]dp[i] += dp[j - 1] * dp[i - j];3、dp数组如何初始化dp[0] = 1，dp[1] = 1;
二、背包问题系列2.1 01背包系列二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。倒序遍历的原因：是为了保证物品i只被放入一次。2.1.1分割等和子集 【背包能不能装满】给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。解题思路是：target = nums数组和 如果是奇数直接return false；如果是偶数，那么我们的背包容量就确定为target/2如果最后dp[target/2] == target/2 return true;否则false 1、确定dp数组以及下标的含义dp[i]：背包容量为i，所装物品的价值最大为dp[i]2、确定递推公式对于每一个物品来说无非就是装不装两种选择【滚动数组】前提：if(i-nums[i]>0)装：dp[i-nums[i]]+nums[i]不装：dp[i]dp[i] = Math.max(dp[i], dp[i-nums[i]]+nums[i])3、dp数组如何初始化dp[0] = 0;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历
2.1.2最后一块石头的重量
【背包最多能装多少】有一堆石头，每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。解题思路是：target = nums数组和我们的背包容量就确定为target/2最后查看背包装了多少dp[target/2]剩余的另一堆石头：target-dp[target/2]相减： target-dp[target/2] - dp[target/2] 即为最后结果 1、确定dp数组以及下标的含义dp[i]：背包容量为i，所装物品的价值最大为dp[i]2、确定递推公式对于每一个物品来说无非就是装不装两种选择【滚动数组】装：dp[i-stones[i]]+stones[i]不装：dp[i]dp[i] = Math.max(dp[i], dp[i-stones[i]]+stones[i])3、dp数组如何初始化dp[0] = 0;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历
2.1.3 目标和【装满背包有多少种方法】给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数一波数学推导：add 【+符号的】 sub【-符号的】sum= add+subtarget = add-sub因此：add = (sum+target)/2 也就是我们的背包容量 如果是奇数，说明无解，直接返回0即可。同时如果 S的绝对值已经大于sum，那么也是无解的。 1、确定dp数组以及下标的含义dp[i]：背包容量为i，装满背包i 有dp[i]种方法2、确定递推公式只要搞到nums[j]，凑成dp[i]就有dp[i- nums[j]] 种方法。dp[i] += dp[i-nums[j]]例如：dp[j]，j 为5，已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。3、dp数组如何初始化dp[0] = 1;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历
求组合类问题的公式，都是类似这种：dp[j] += dp[j - nums[i]]
2.1.4 一和零【装满这个背包最多有多少个物品】一个二进制字符串数组 strs 和两个整数 m 和 n 。找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 1、确定dp数组以及下标的含义dp[i][j]：i个0 j个1时，背包中最多有dp[i][j]个子集2、确定递推公式这个子集放还是不放放进去：dp[i][j] = dp[i -numZero][j-numOne]+1不放进去：dp[i][j] = dp[i][j]dp[i][j] = Math.max(dp[i][j], dp[i -numZero][j-numOne]+1 )3、dp数组如何初始化dp[0] = 0;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历
2.2 完全背包系列每个物品都可以重复使用，因此对于背包容量的遍历由从后向前变为从前向后.完全背包的两个for循环的先后顺序都是可以的。== 外层for循环遍历物品，内层for遍历背包的情况，这种遍历顺序中dp[j]里计算的是组合数==外层for遍历背包的情况，内层for循环遍历物品，这种遍历顺序中dp[j]里计算的是排列数2.2.1零钱兑换
【组合数】给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。5 = 2 + 2 + 15 = 2 + 1 + 2这是一种组合，都是 2 2 1。如果问的是排列数，那么上面就是两种排列了。组合不强调元素之间的顺序，排列强调元素之间的顺序。 1、确定dp数组以及下标的含义dp[j]：凑成金额 j 有dp[j]种方法2、确定递推公式dp[j] += dp[j-coins[i]]3、dp数组如何初始化dp[0] = 1;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从前向后遍历
2.2.2组合总和Ⅳ【组合数】给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。 1、确定dp数组以及下标的含义dp[j]：凑成目标 j 有dp[j]种方法2、确定递推公式dp[j] += dp[j-nums[i]]3、dp数组如何初始化dp[0] = 1;4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从前向后遍历
2.2.3爬楼梯（完全背包解法）【排列数】正在爬楼梯。需要 n 阶你才能到达楼顶，每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶呢？把一次可以上的阶梯数 看作物品 weight {1,2}; 如果一个可以爬m阶都可以放入物品数组当中 1、确定dp数组以及下标的含义dp[j]：爬到 j层 有dp[j]种方法2、确定递推公式dp[j] += dp[j-weight[i]]3、dp数组如何初始化dp[0] = 1;4、遍历顺序外层for循环遍历背包容量，内层for循环遍历物品
2.2.4零钱兑换【装满背包的最少物品】给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。 1、确定dp数组以及下标的含义dp[j]：凑成目标 j 最少的硬币个数为dp[j]2、确定递推公式dp[j] = Math.min(dp[j], dp[j-coins[i]]+1)并且：只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要3、dp数组如何初始化dp[0] = 0;其他值应该是最大值。4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从前向后遍历
2.2.5完全平方数【装满背包的最少物品】给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 1、确定dp数组以及下标的含义dp[j]：凑成目标 j 最少的完全平方数为dp[j]2、确定递推公式dp[j] = Math.min(dp[j], dp[j-ii]+1)并且：只有dp[j-ii]不是初始最大值时，该位才有选择的必要3、dp数组如何初始化dp[0] = 0;其他值应该是最大值。4、遍历顺序外层for循环遍历物品，内层for循环遍历背包容量且从前向后遍历
2.2.6单词拆分【物品能不能把背包装满】※给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 1、确定dp数组以及下标的含义dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。2、确定递推公式如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !valid[i]; j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}
3、dp数组如何初始化dp[0] = true;4、遍历顺序外层for循环遍历背包容量，内层for循环遍历物品
三、打家劫舍系列3.1打家劫舍 打家劫舍（力扣198）相邻的两间房子会触发警报对于每一间房子都有偷和不偷两种状态dp[j]:考虑下标j（包括j）以内的房屋，最多可以偷窃的金额为dp[j]。初始化dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);dp[j] = max(dp[j-1],dp[j-2]+nums[j])
3.2打家劫舍
【成环】 打家劫舍
（力扣213）相邻的两间房子会触发警报并且首尾成环分为三种情况：情况一：不考虑首位情况二：不考虑首情况三：不考虑尾情况二三都包含了情况一，因此只考虑情况二三即可最后返回max(情况二，情况三)
3.3打家劫舍
【树状】 打家劫舍 III（力扣337）树状确定遍历顺序–>后序遍历每个结点分为偷和不偷两种情况根节点不偷dp[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);根节点偷dp[1] = root.val + left[0] + right[0];
四、股票系列4.1买卖股票的最佳时机【只能买卖一次】 dp[i][0]:持有股票的状态dp[i][1]:不持有股票的状态dp[0][0] = -prices[0];dp[0][1] = 0;dp[i][0] = max(dp[i-1][0], -prices[i])dp[i][1] = max(dp[i-1][1] , dp[i-1][0]+prices[i])
4.2买卖股票的最佳时机
【可以买卖多次】 dp[i][0]:持有股票的状态dp[i][1]:不持有股票的状态dp[0][0] = -prices[0];dp[0][1] = 0;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])细微变化在于持有股票状态的递推过程
4.3买卖股票的最佳时机
【最多买卖2次】 dp[i][0] 不操作dp[i][1]:第一次持有股票状态dp[i][2]:第一次不持有股票状态dp[i][3]:第二次持有股票状态dp[i][4]:第二次不持有股票状态初始化dp[0][0]= 0dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[i][0] = dp[i-1][0]dp[i][1] = max(dp[i-1][1],-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[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
4.4买卖股票的最佳时机IV 【最多买卖k次】 dp[i][0] 不操作dp[i][1]:第一次持有股票状态dp[i][2]:第一次不持有股票状态dp[i][3]:第二次持有股票状态dp[i][4]:第二次不持有股票状态……0 ----- 2*k奇数是持有股票状态偶数是卖出股票状态初始化时：if(j%2==1) dp[0][j] = -prices[0];奇数时：dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i])偶数时：dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] +prices[i])
4.5最佳买卖股票时机含冷冻期 【买卖多次，卖出后有一天是冷冻期】 dp[i][0]:持有股票的状态dp[i][1]:保持卖出股票的状态dp[i][2]:卖出股票的状态dp[i][3]:冷冻期初始化dp[0][0] = -prices[0];dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i], dp[i-1][3]- prices[i])dp[i][1] = max(dp[i-1][1], dp[]i-1[3])dp[i][2] = dp[i-1][0]+prices[i]dp[i][3] = dp[i-1][2]
4.6买卖股票的最佳时机含手续费【买卖多次，每次都有手续费】 dp[i][0]:持有股票的状态dp[i][1]:不持有股票的状态dp[0][0] = -prices[0]-fee;dp[0][1] = 0;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])细微变化在于多减去手续费
五、子序列问题5.1子序列（不连续）5.1.1最长上升子序列 ※给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 1、确定dp数组以及下标的含义dp[i]：下标为i以内（包括i）找到的最长递增子序列长度为dp[i]2、确定递推公式if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);3、dp数组如何初始化每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.4、遍历顺序从左到右
5.1.2最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 1、确定dp数组以及下标的含义dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j] 【i-1、j-1的原因就是为了初始化的时候方便】2、确定递推公式相等的情况下 nums[i-1] == nums[j-1]dp[i][j] = dp[i-1][j-1]+1不相等的情况下dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) 【两边都可以进行删除】3、dp数组如何初始化dp[0][0] = 0;4、遍历顺序从左到右
5.1.3不相交的线【与5.1.2最长公共子序列几乎一样】5.2子序列（连续）5.2.1最长连续递增序列给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。 1、确定dp数组以及下标的含义dp[i]：下标为i以内（包括i）找到的最长连续递增的子序列长度为dp[i]2、确定递推公式if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1);3、dp数组如何初始化每一个i，对应的dp[i]起始大小至少都是1.4、遍历顺序从左到右
5.2.2最长重复子数组给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 1、确定dp数组以及下标的含义dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j] 【i-1、j-1的原因就是为了初始化的时候方便】2、确定递推公式相等 nums[i-1]==nums[j-1]dp[i][j] = dp[i-1][j-1]+13、dp数组如何初始化dp[0][0] = 04、遍历顺序从左到右
5.2.3最大子序和 ※给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 1、确定dp数组以及下标的含义dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。2、确定递推公式dp[i]只有两个方向可以推出来：dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和nums[i]，即：从头开始计算当前连续子序列和3、dp数组如何初始化dp[0] = nums[0]4、遍历顺序从左到右
5.3编辑距离5.3.1判断子序列【不连续】给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 1、确定dp数组以及下标的含义dp[i][j]：以下标i - 1为结尾的A是以下标j - 1为结尾的B的子序列，那么dp[i][j] = true2、确定递推公式相等的情况下 s[i-1] == t[j-1]dp[i][j] = dp[i-1][j-1]+1不相等的情况下dp[i][j] = dp[i][j-1] 【只能删除t不能删除s】3、dp数组如何初始化dp[0][0] = 0;4、遍历顺序从左到右
5.3.2不同的子序列 【不连续----hard】※给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 1、确定dp数组以及下标的含义dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。2、确定递推公式s[i-1] == t[j-1]dp[i][j] = dp[i-1][j-1] (使用s[i-1]这个元素) + dp[i-1][j](不使用s[i-1]这个元素 使用s[i-1]之前的元素)那么如果不相等的话 else dp[i][j] = dp[i-1][j] 也就是不使用s[i-1]这个元素3、dp数组如何初始化dp[i][0] —> s[i-1] t[-1] -1相当于是空字符串，t是空字符号串 s不是空的，s中的元素全部删除之后我们的s就变成了空字符串，因此只有这一种方法使s变成t。dp[i][0] = 1;dp[0][j] —> s[-1] t[j-1] s是空字符串 t不是空的，没有任何一种方法可以使s变成t，因此dp[0][j] =0;这两个中间有一个交集 dp[0][0] —> s是空字符串 t是空字符串 有一种方法可以让s变成t。因此dp[0][0] = 1;4、遍历顺序从左到右
5.3.3两个字符串的删除操作给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。与上一题相比两个字符都可以删除 1、确定dp数组以及下标的含义dp[i][j]：以i-1为结尾的word1子序列与以j-1为结尾的word2相同所需要的最小步数为dp[i][j]。2、确定递推公式相等的情况：不操作dp[i][j] = dp[i-1][j-1]不相等的情况：可以删除word1也可以删除word2：dp[i][j] = min(dp[i-1][j] , dp[i][j-1])+13、dp数组如何初始化for(int i=0;i<word1.length();i++) dp[i][0] = ifor(int j=0;j<word2.length();i++) dp[0][j] = j4、遍历顺序从左到右
也可以求两个字符串的最长公共子序列是多少，然后最后两个字符串长度相加减去2倍的公共子序列长度即可 参考5.1.2最长公共子序列5.3.4编辑距离给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符 1、确定dp数组以及下标的含义dp[i][j]：以i-1为结尾的word1子序列与以j-1为结尾的word2相同所需要的最小步数为dp[i][j]。2、确定递推公式相等的情况：不操作dp[i][j] = dp[i-1][j-1]不相等的情况：1、删除操作：可以删除word1也可以删除word2：dp[i][j] = min(dp[i-1][j] , dp[i][j-1])+12、插入操作：和删除操作为逆操作 因此递推公式一致3、替换操作：dp[i-1][j-1]+1因此，递推公式为：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )+13、dp数组如何初始化for(int i=0;i<word1.length();i++) dp[i][0] = ifor(int j=0;j<word2.length();i++) dp[0][j] = j4、遍历顺序从左到右
5.4回文5.4.1回文子串【连续】给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 1、确定dp数组以及下标的含义布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。2、确定递推公式相等： s[i] == s[j]情况一：i==j dp[i][j] = true “a”情况二：j-1=1 dp[i][j] = true “aa”情况三：j-i >1 dp[i][j] = dp[i+1][j-1];不相等：s[i] !=s[j]dp[i][j] = false3、dp数组如何初始化都为false4、遍历顺序从下到上 从左到右一个true 结果res++ 最后直接return res
5.4.2最长回文子序列【不连续】给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 1、确定dp数组以及下标的含义布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）最长的回文子序列长度为dp[i][j]2、确定递推公式相等： s[i] == s[j]dp[i][j] =dp[i+1][j-1]+2不相等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])3、dp数组如何初始化对角线=1 dp[i][i] = 14、遍历顺序从下到上 从左到右