网站提交 入口,学历提升快速拿证,深圳网站建设平台,wordpress 下载列表插件115.不同的子序列
题目
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 109 7 取模。
数据范围
1 s.length, t.length 1000s 和 t 由英文字母组成
分析
令dp[i][j]为s的前i个字符构成的子序列中为t的前j…115.不同的子序列
题目
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。
数据范围
1 s.length, t.length 1000s 和 t 由英文字母组成
分析
令dp[i][j]为s的前i个字符构成的子序列中为t的前j个字符的数量接下来设置边界条件当t为空时s前i个字符构成子序列只要空字符串满足个数为1即dp[i][0]1考虑状态转移 当 s [ i ] ! t [ j ] d p [ i 1 ] [ j 1 ] d p [ i ] [ j ] 当s[i]!t[j]dp[i 1][j 1] dp[i][j] 当s[i]!t[j]dp[i1][j1]dp[i][j] 当 s [ i ] t [ j ] d p [ i 1 ] [ j 1 ] d p [ i ] [ j ] d p [ i ] [ j 1 ] ; 当s[i]t[j]dp[i1][j1] dp[i][j] dp[i][j 1]; 当s[i]t[j]dp[i1][j1]dp[i][j]dp[i][j1];
代码
class Solution {
public: const static int N 1005, mod 1e9 7;int dp[N][N];int numDistinct(string s, string t) {if(s.size() t.size()) return 0;for(int i 0; i s.size(); i ) dp[i][0] 1;for(int i 0; i s.size(); i ) {for(int j 0; j i j t.size(); j ) {if(s[i] ! t[j]) dp[i 1][j 1] dp[i][j 1];else dp[i 1][j 1] dp[i][j] dp[i][j 1];dp[i 1][j 1] % mod;}} return dp[s.size()][t.size()];}
};63.不同路径Ⅱ
题目
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为“Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。
数据范围
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
分析
令dp[i][j]为到那个格子的路径数考虑状态转移
如果有障碍物 d p [ i ] [ j ] 0 dp[i][j]0 dp[i][j]0没有障碍物 d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i ] [ j − 1 ] dp[i][j]dp[i-1][j]dp[i][j-1] dp[i][j]dp[i−1][j]dp[i][j−1]
代码
class Solution {
public:const static int N 105;int dp[N][N];int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int n obstacleGrid.size(), m obstacleGrid[0].size();for(int i 0; i n; i ) {for(int j 0; j m; j ) {if(!i !j !obstacleGrid[i][j]) {dp[i 1][j 1] 1;continue;}if(obstacleGrid[i][j]) dp[i 1][j 1] 0;else dp[i 1][j 1] dp[i][j 1] dp[i 1][j]; }}return dp[n][m];}
};746.使用最小花费爬楼梯
题目
给你一个整数数组 cost 其中cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围
2 cost.length 10000 cost[i] 999
分析
令dp[i]为到达那一层的最小花费状态转移 d p [ i ] m i n ( d p [ i − 1 ] c o s t [ i − 1 ] , d p [ i − 2 ] c o s t [ i − 2 ] ) dp[i]min(dp[i-1]cost[i - 1],dp[i-2] cost[i - 2]) dp[i]min(dp[i−1]cost[i−1],dp[i−2]cost[i−2])
代码
class Solution {
public:const static int N 1005;int dp[N];int minCostClimbingStairs(vectorint cost) {dp[0] dp[1] 0;for(int i 2; i cost.size(); i ) {dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
};
