动态规划法!!!
dp[i][j]=true
表示字符串从下标 i 到下标 j 的位置是一个回文子串(所谓的状态转移)
var longestPalindrome = function(s) {
let len=s.length;
let dp=[];
for(let i=0;i<len;i++){
dp[i]=[];
dp[i][i]=true;
}
let start=0,maxlen=1;
for(let j=1;j<len;j++){
for(let i=0;i<len-1;i++){
if(s[i]==s[j]){
if(j-i<=2){
dp[i][j]=true;
}else{
dp[i][j]=dp[i+1][j-1];
}
}else{
dp[i][j]=false;
}
if(dp[i][j]==true&&j-i+1>maxlen){
maxlen=j-i+1;
start=i;
}
}
}
return s.substr(start,maxlen);
};
扩展练习
对于一个由大写英文字母和“*”
号组成的字符串,求它的最长回文子串的长度,其中一个“*”
号可以用来替代任意一个字符。
// 样例输入:DAB*B*ACD
// 样例输出: 6
let s='DAB*B*ACD'
let len=s.length;
let dp=[];
let start=0,maxlen=1;
for(let i=0;i<s.length;i++){
dp[i]=[];
dp[i][i]=true
}
for(let j=1;j<len;j++){
for(let i=0;i<len;i++){
if(s[i]==s[j]||s[i]=='*'||s[j]=='*'){
if(j-i<=2){
dp[i][j]=true;
}else{
dp[i][j]=dp[i+1][j-1];
}
}else{
dp[i][j]=false;
}
if((j-i+1>maxlen)&&(dp[i][j]==true)){
maxlen=j-i+1;
start=i;
}
}
}
console.log(maxlen)
动态规划练习
解析:
dp[i][j]表示长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]
(1)若当前字符相同,dp[i][j]=dp[i-1][j-1]+1
(2)若当前字符不相同,dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
var longestCommonSubsequence = function(text1, text2) {
let len1=text1.length;
let len2=text2.length;
let dp=Array.from(Array(len1+1),()=>Array(len2+1).fill(0));
for(let i=1;i<=len1;i++){
for(let j=1;j<=len2;j++){
if(text1[i-1]==text2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[len1][len2];
};
状态转移方程为 dp[n] = (dp[n-3] + dp[n-2] + dp[n-1])%(1000000007)
var waysToStep = function(n) {
if(n<=2)return n;
let dp=new Array(n);
dp[0]=1,dp[1]=2,dp[2]=4;
for(let i=3;i<n;i++){
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007;
}
return dp[n-1];
};
var maxSubArray = function(nums) {
let dp=[],max=nums[0];
dp[0]=nums[0];
for(let i=1;i<nums.length;i++){
if(dp[i-1]>0){
dp[i]=nums[i]+dp[i-1];
}else{
dp[i]=nums[i];
}
max=(dp[i]>max)?dp[i]:max;
}
return max;
};
(进步:没看解题思路!)
官方的状态方程是dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]),最后的dp[len]即为最大金额
我找的状态方程是dp[i]=nums[i-1]+Math.max(dp[i-2],dp[i-3]),需要另用一个变量maxnum存放最大值,并每次比较,记录最大的那个,最后输出
(上述的nums[i-1]是因为遍历从1开始)
var rob = function(nums) {
let len=nums.length;
let maxnum=0;
let dp=new Array(len+1);
dp[0]=0;
for(let i=1;i<=len;i++){
if(i<3){
dp[i]=nums[i-1];
}else{
dp[i]=nums[i-1]+Math.max(dp[i-2],dp[i-3]);
}
maxnum=(dp[i]>maxnum)?dp[i]:maxnum;
}
return maxnum;
};
状态方程为dp[i][j]=dp[i][j-1]+dp[i-1][j]
var uniquePaths = function(m, n) {
let dp=Array.from(Array(m+1),()=>Array(n+1).fill(0));
for(let i=1;i<=m;i++){
for(let j=1;j<=n;j++){
if(i==1&&j==1){
dp[i][j]=1;
}else{
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
}
return dp[m][n]
};
难点:要构建两个一位数组,分别存放小于位置 i 元素的乘积(left)和大于位置 i 元素的乘积(right)
其中,分别设置两个变量 i、j,i 从起始位置开始,j 从末尾位置开始
left的状态方程:left[i]=left[i-1]*a[i-1],left[1]==1
right的状态方程:right[j]=right[j+1]*a[j+1],right[j]==1
var constructArr = function(a) {
let left=[];
let right=[];
let index=0;
for(let i=0;i<a.length;i++){
let j=a.length-i-1;
if(i==0&&j==a.length-1){
left[i]=1;
right[j]=1;
}else{
left[i]=left[i-1]*a[i-1];
right[j]=right[j+1]*a[j+1];
}
}
for(let i=0;i<a.length;i++){
a[i]=left[i]*right[i];
}
return a;
};
注意,此处的状态方程与不同路径的类似,但需注意第一列和第一行的状态方程
第一行:dp[i][j]=grid[i-1][j-1]+dp[i][j-1]
第一列:dp[i][j]=grid[i-1][j-1]+dp[i-1][j]
其余:dp[i][j]=grid[i-1][j-1]+Math.min(dp[i-1][j],dp[i][j-1])
var minPathSum = function(grid) {
let m=grid.length;
let n=grid[0].length;
let dp=Array.from(Array(m+1),()=>Array(n+1).fill(0));
for(let i=1;i<=m;i++){
for(let j=1;j<=n;j++){
if(i==1){
dp[i][j]=grid[i-1][j-1]+dp[i][j-1];
}
else if(j==1){
dp[i][j]=grid[i-1][j-1]+dp[i-1][j];
}
else dp[i][j]=grid[i-1][j-1]+Math.min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)