斐波那契数列 跳台阶问题

var fib = function (n,memo) {
    if(n <= 2) return n
    if(memo[n]) return memo[n] //缓存记录
    n = fib(n - 1,memo) + fib(n - 2,memo)
    return n
}

var fib = function (n){
    if(n <= 1) return n

    // let dp = [0,1]
    // for(let i=2;i<=n;i++){
    //   dp[i] = dp[i-1]+dp[i-2]
    // }
    // return dp[n]


    let dp1=0,dp2=1,dp3
    for(let i = 2;i <= n;i++){
        dp3 = dp1 + dp2
        dp1 = dp2
        dp2 = dp3
    }
    return dp3


}

硬币兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1

// 时间复杂度：O(Sn)O(Sn)O(Sn)，其中 SSS 是金额，nnn 是面额数。空间复杂度O(S)

var coinChange = function (coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity) // 初始化dp数组
    dp[0] = 0 // dp[0]表示凑成0所需的最少硬币个数 

    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            // 遍历每种硬币的兑换数量
            if (coins[j] <= i) {
                //
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
}

最长回文字串

// 暴力解法  时间复杂度O(n^2)
var longestPalindrome = function(s) {
    let i=0,j=s.length,str='';

    function isCallBack(str){
        let left=0,right=str.length-1;
        while(left<right){
            if(str[left]!==str[right]){
                return false;
            }else{
                left++;
                right--;
            }
        }
        return true;
    }

    while(i<s.length){
        while(i<j){
            const tem = s.slice(i,j);
            if(tem.length<str.length){
                break;
            }
            if(isCallBack(tem)){
                str = tem;
                break;
            }else{
                j--;
            }
        }
        i++;
        j=s.length;
    }

    return str;
};