动态规划几个例题！！

动态规划法！！！
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;//start为开始位置，maxlen为长度
    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(s.substr(start,maxlen));
console.log(maxlen)//6

动态规划练习

解析：
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;
    //初始化dp数组,len1+1行,len2+1列,并初始化为0
    let dp=Array.from(Array(len1+1),()=>Array(len2+1).fill(0));
    // 从左往右从上往下遍历，位置从1开始，方便计算dp[i][j]的值
    for(let i=1;i<=len1;i++){
        for(let j=1;j<=len2;j++){
            if(text1[i-1]==text2[j-1]){//此时字符串的位置都要-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=[];//存放小于i的乘积
    let right=[];//存放大于i的乘积
    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];
    }
    // console.log(left,right)
    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];
};