工信部网站备案举报,今天佛山突发新闻,网站开发项目付款方式,小米品牌vi设计931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix #xff0c;请你找出并返回通过matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始#xff0c;并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列#xff08;即…931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。具体来说位置 (row, col) 的下一个元素应当是 (row 1, col - 1)、(row 1, col) 或者 (row 1, col 1) 。
数据范围
n matrix.length matrix[i].length1 n 100-100 matrix[i][j] 100
分析
简单dp
代码
class Solution {
public:int res 0x3f3f3f3f;int n;const static int N 105;int dp[N][N];int minFallingPathSum(vectorvectorint matrix) {n matrix.size();for(int i 1; i n; i ) {for(int j 1; j n; j ) {if(j 1) dp[i][j] min(dp[i - 1][j], dp[i - 1][j 1]) matrix[i - 1][j - 1];else if(j n) dp[i][j] min(dp[i - 1][j], dp[i - 1][j - 1]) matrix[i - 1][j - 1];else {dp[i][j] min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i - 1][j - 1];}}}int res 0x3f3f3f3f;for(int i 1; i n; i ) res min(res, dp[n][i]);return res;}
};516. 最长回文子序列
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
数据范围
1 s.length 1000s 仅由小写英文字母组成
分析
令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示下标j到i的最长回文子序列长度状态转移如下 若 s [ i ] s [ j ] d p [ i ] [ j ] m a x ( d p [ i ] [ j 1 ] , m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j 1 ] 2 ) ) 其中 d p [ i ] [ j 1 ] 表示 j 1 到 i 的最长子序列 d p [ i − 1 ] [ j 1 ] 2 指使用 s [ i ] 和 s [ j ] 作为回文子序列的首尾 若s[i]s[j] \ dp[i][j]max(dp[i][j1],max(dp[i-1][j],dp[i-1][j1]2))其中dp[i][j1]表示j1到i的最长子序列dp[i-1][j1]2指使用s[i]和s[j]作为回文子序列的首尾 若s[i]s[j] dp[i][j]max(dp[i][j1],max(dp[i−1][j],dp[i−1][j1]2))其中dp[i][j1]表示j1到i的最长子序列dp[i−1][j1]2指使用s[i]和s[j]作为回文子序列的首尾 若 s [ i ] ! s [ j ] d p [ i ] [ j ] m a x ( d p [ i ] [ j 1 ] , d p [ i − 1 ] [ j ] ) 此时无法使用 s [ i ] 和 s [ j ] 作为首尾 若s[i]!s[j] \ dp[i][j]max(dp[i][j1],dp[i-1][j])此时无法使用s[i]和s[j]作为首尾 若s[i]!s[j] dp[i][j]max(dp[i][j1],dp[i−1][j])此时无法使用s[i]和s[j]作为首尾 由于 d p [ i ] [ j 1 ] dp[i][j1] dp[i][j1]需要使用上一次的数据因此这里j需要倒着遍历
代码
class Solution {
public:const static int N 1005;int dp[N][N];int longestPalindromeSubseq(string s) {int n s.size();dp[0][0] 1;for(int i 0; i n; i ) dp[i 1][i 1] 1;for(int i 0; i n; i ) {for(int j i - 1; j 0 ; j -- ) {dp[i 1][j 1] max(dp[i 1][j 2], dp[i][j 1]);if(s[i] s[j]) {dp[i 1][j 1] max(dp[i 1][j 1], dp[i][j 2] 2);} }}int res 0;for(int i 1; i n; i ) res max(res, dp[n][i]);return res;}
};712. 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
数据范围
0 s1.length, s2.length 1000s1 和 s2 由小写英文字母组成
分析
令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示 s 1 s1 s1的前 i i i个字符和 s 2 s2 s2的前 j j j个字符变相等所需要删除 a s c l l ascll ascll字符的最小值 状态转移如下 若 s 1 [ i ] s 2 [ j ] d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] a , m i n ( d p [ i ] [ j − 1 ] b , d p [ i − 1 ] [ j − 1 ] ) ) ; 若s1[i]s2[j]\ dp[i][j]min(dp[i - 1][j] a, min(dp[i][j - 1] b, dp[i - 1][j - 1])); 若s1[i]s2[j] dp[i][j]min(dp[i−1][j]a,min(dp[i][j−1]b,dp[i−1][j−1])); 若 s 1 [ i ] ! s 2 [ j ] d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] a , m i n ( d p [ i ] [ j − 1 ] b , d p [ i − 1 ] [ j − 1 ] a b ) ) 若s1[i]!s2[j]\ dp[i][j] min(dp[i - 1][j] a, min(dp[i][j - 1] b, dp[i - 1][j - 1] a b)) 若s1[i]!s2[j] dp[i][j]min(dp[i−1][j]a,min(dp[i][j−1]b,dp[i−1][j−1]ab)) 其中 a a a是 s 1 [ i ] s1[i] s1[i]的ascll值b是 s 2 [ j ] s2[j] s2[j]的ascll值 注意一下初始化 d p [ i ] [ 0 ] dp[i][0] dp[i][0]和 d p [ 0 ] [ j ] dp[0][j] dp[0][j]就是将对应的 s 1 s1 s1的前 i i i个全删除s2的前 j j j个全删除
代码
class Solution {
public:const static int N 1005;int dp[N][N];int minimumDeleteSum(string s1, string s2) {int n s1.size(), m s2.size();memset(dp, 0x3f, sizeof(dp));dp[0][0] 0;for(int i 0; i n; i ) dp[i 1][0] dp[i][0] (int)s1[i];for(int j 0; j m; j ) dp[0][j 1] dp[0][j] (int)s2[j];for(int i 1; i n; i ) {for(int j 1; j m; j ) {int a (int)s1[i - 1];int b (int)s2[j - 1];if(s1[i - 1] s2[j - 1]) dp[i][j] min(dp[i - 1][j] a, min(dp[i][j - 1] b, dp[i - 1][j - 1]));else dp[i][j] min(dp[i - 1][j] a, min(dp[i][j - 1] b, dp[i - 1][j - 1] a b));}}return dp[n][m];}
};
