动态规划

[includeios]

动态规划

题目 1+1+1+1+1+1

A：上面的等式值是多少呀
B：(奋笔疾书计算)...等于6

A：那在上面的等式前面再写上"1+"呢？1+1+1+1+1+1+1，现在等于多少呀
B：(迅速作答)等于7
A：这次你为什么这么快就算出来了呀？
B：因为这次只要在6的基础上再加1就可以了，不需要再重新计算一遍了

动态规划的核心就是：记住已经解决过的子问题的解。those who cannot remember the past are condemned to repeat it

题目一：斐波拉契数列

fibonacci(0) = 0

fibonacci(1) = 1

fibonacci(n) = fibonacc(n-1) + fibonacc（n-2）

//递归
const fib = (n)=>{
    if(n <= 1) return n
    return fib(n-1)+fib(n-2)
}

• 没个节点都会执行一次，fib(2)执行了5次，时间开销大
• 调用没个函数时需要保留上下文，空间开销也不小
• 把已经执行过的子节点保存起来，后面要用到的时候直接查表读出

//自顶向下的备忘录法
const Memo = []
const fib = (n,Memo)=>{
    //如果备忘录里已经有了记录，直接返回
    if(Memo[n]) return Memo[n]
    
    if(n <= 1)  Memo[n] = n
    else Memo[n] = fib(n-1,Memo) + fib(n-2,Memo)
    
    return Memo[n]
}

fib(6,Memo)

• 依旧使用了递归，计算fib(6)到最后还是要去计算出fib(1)，fib(2)，fib(3) ...
• 为什么不先计算出fib(1)，fib(2)，fib(3)，再去算fib(6)

//自低向上法
const fib(n){
    if(n <= 1) return n
    let Memo_i = 1 //n
    let Memo_i_1 = 1 //1
    let Memo_i_2= 0 //0
    
    for(let i = 2;i<=n;i++){
        Memo_i = Memo_i_1 + Memo_i_2
        Memo_i_2 = Memo_i_1
        Memo_i_1 = Memo_i
    }
    
    return Memo_i
}

最长回文子串

dp[i][j] = 1  //s.substr(i，j)是回文串

const longestPalindrome = (s)=>{
	const len = s.length
    if(len <= 1) return s
    let start = 0//回文串起始位置
    let max = 1  //回文串最大长度
    
    const dp = [][]
    
    //首先计算长度为1和长度为2的子回文串
    for(let i = 0;i<len;i++){
        dp[i][i] = 1
        if(i<len - 1 && s[i] == s[i+1]){
            dp[i][i+1] = 1
            max = 2
            start=i
        }
    }
    
    //从计算长度为3的子回文串开始,一直到计算长度为length的子回文串
    for(let l = 3;l<=len;l++){
        for(let i = 0;i+l<=len;i++){
            const j = i+l-1 //终止字符位置
            if(s[i] == s[j] && dp[i+1][j-1] == 1){
                dp[i][j] = 1
                start = i
                max = l
            }
        }
    }
    
    return s.substr(start,max)
}