我们一起聊聊十五周算法训练营中的普通动态规划

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

// 递归的形式试试(这种形式可定不满足面试官要求，从而超时，但是在这个基础上可以改成备忘录，备忘录之后进而改成动态规划)
function lengthOfLIS1(nums) {

    // 该递归函数表示以nums[index]结尾的部分的最长递增子序列值
    const helper = (nums, index) => {
        // 边界条件
        if (index === 0) {
            return 1;
        }

        let result = 1;
        for (let i = 0; i < index; i++) {
            // 获取子问题结果
            const subproblem = helper(nums, i);

            // 然后判断nums[i] 与nums[index]的大小
            if (nums[i] < nums[index]) {
                result = Math.max(result, subproblem + 1);
            }
        }

        return result;
    };

    let result = 0;

    // 因为最长递增子序列有可能以任意值结果，所以遍历一遍找到最大
    for (let i = 0; i < nums.length; i++) {
        result = Math.max(helper(nums, i), result);
    }

    return result;
}

// 备忘录形式进行优化
function lengthOfLIS2(nums) {
    const map = new Map();

    const helper = (nums, index) => {
        if (index === 0) {
            return 1;
        }

        if (map.has(index)) {
            return map.get(index);
        }
        let result = 1;

        for (let i = 0; i < index; i++) {
            const subproblem = helper(nums, i);

            if (nums[i] < nums[index]) {
                result = Math.max(result, subproblem + 1);
            }
        }

        return result;
    };

    let result = 1;

    for (let i = 0; i < nums.length; i++) {
        result = Math.max(result, helper(nums, i));
    }

    return result;
}

// 设计动态规划算法，需要一个dp数组，假设dp[0……i-1]已经被算出来了，然后根据这些结果算出来dp[i]

// 在该问题中，dp数组的含义是：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度
// 根据这个定义可以推出bad case：dp[i]初始值为1，因为以nums[i]结尾的最长递增子序列起码要包含它自己

// 如何找到动态规划的状态转移关系
// 1. 明确dp数组所存数据的含义
// 2. 根据dp数组的含义，运用数学归纳法的思想，假设dp[0……i-1]都已知，想办法求出dp[i],一旦这一步完成，整个题目基本就解决了

function lengthOfLIS3(nums) {
    // 初始化dp数组,dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度，其中最小为1
    const dp = new Array(nums.length).fill(1);

    let result = 0;
    // 遍历一遍
    for (let i = 0; i < nums.length; i++) {
        // 要找到以i为结尾的最长递增子序列，就是前面i - 1项中存在的最长递增子序列 + 1，通过比较获取其最大的
        for (let j = 0; j < i; j++) {
            // 当nums[j]的值小于[i]的值时,才满足递增子序列的要求
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        // 获取从0-n中最长的
        result = Math.max(result, dp[i]);
    }

    return result;
}

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS1(nums));
console.log(lengthOfLIS2(nums));
console.log(lengthOfLIS3(nums));

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace” 输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

// 既然是最值问题，肯定优先考虑动态规划
// 对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划的思路
// 首先写一个dp函数：
// 定义：计算 s1[0……i] 和 s2[0……j] 的最长公共子序列长度
// int dp(String s1, int i, String s2, int j)
// 这个dp函数的定义是：dp(s1, i, s2, j)计算s1[0……i]和s2[0……j]的最长公共子序列长度。
// 根据这个定义，那么我们想要的答案就是dp(s1, s1.length, s2, s2.length)，且 base case 就是i < 0或j < 0时，因为这时候s1[0……i]或s2[0……j]就相当于空串了，最长公共子序列的长度显然是 0
// 如果在求dp[i][j]的时候，此时会出现以下几种情况：
// 1. 如果text1[i] === text2[j],此时证明该字符在该lcs中，则dp[i][j] = dp[i - 1][j - 1] + 1;
// 2. 如果text1[i] !== text2[j],此时可能：
// （1）text1[i]不在lcs中；
// （2) text2[j]不在lcs中；
// （3）text1[i]和text2[j]都不在lcs中
// 则dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]),注：dp[i - 1][j - 1]可以被省略,因为多一个字符去比较肯定比少一个字符去比较结果长

// 暴力递归
function longestCommonSubsequence1(text1, text2) {
    const dp = (text1, i, text2, j) => {
        // base case
        if (i < 0 || j < 0) {
            return 0;
        }

        if(text1[i] === text2[j]) {
            return dp(text1, i - 1, text2, j - 1) + 1;
        } else {
            return Math.max(dp(text1, i - 1, text2, j), dp(text1, i, text2, j - 1), dp(text1, i - 1, text2, j - 1));
        }
    };

    return dp(text1, text1.length - 1, text2, text2.length - 1);
}

// 备忘录法
function longestCommonSubsequence2(text1, text2) {
    // 用一个二维数组去存储对应的结果值，在递归的时候首先判断是否存在这样的结果，有的话直接返回
}

// 改成动态规划的形式
// 首先判断是否具备最优子结构，只有具备最优子结构，才能通过子问题得到原问题的最值
// 紧接着找到正确的状态转移方程
// 1. 明确状态：本题的状态就是text1[0……i]和tex2[0……j]的最长子序列
// 2. 定义dp数组/函数：dp[i][j]表示text1[0……i]和tex2[0……j]的最长子序列
// 3. 明确选择：为了获取dp[i][j],需要指导dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]
// 4. 明确base case:此处的base case就是i < 0或j < 0,这个时候一个串为空，最长公共子序列长度就为0
function longestCommonSubsequence3(text1, text2) {
    // 定义dp
    const dp = new Array(text1.length + 1);
    for (let i = 0; i < dp.length; i++) {
        // base case
        dp[i] = (new Array(text2.length + 1)).fill(0);
    }

    for (let i = 1; i < dp.length; i++) {
        for (let j = 1; j < dp[0].length; 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[dp.length - 1][dp[0].length - 1];
}

const text1 = 'abcde';
const text2 = 'ace';

console.log(longestCommonSubsequence1(text1, text2));
console.log(longestCommonSubsequence3(text1, text2));

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

const nums = [1, 2, 3, 1];

// 暴力递归方式
function rob1(nums) {
    const dp = (nums, start) => {
        // 设定递归结束条件
        if (start >= nums.length) {
            return 0;
        }

        // dp(nums, start + 1)表示不抢，去下一家
        // nums[start] + dp(nums, start + 2)表示抢，去下下家
        const result = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));

        return result;
    };

    return dp(nums, 0);
}

console.log(rob1(nums));

// 带备忘录的递归解法
function rob2(nums) {
    const map = new Map();

    const dp = (nums, start) => {
        if (map.has(start)) {
            return map.get(start);
        }

        if (start >= nums.length) {
            return 0;
        }

        const result = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));

        map.set(start, result);

        return result;
    }

    return dp(nums, 0);
}

console.log(rob2(nums));

// 动态规划
function rob3(nums) {
    const n = nums.length;
    const map = new Map();

    // 当超出房间后，抢到的都为0
    map
    .set(n, 0)
    .set(n + 1, 0);
    for (let i = n - 1; i >= 0; i--) {
        map.set(i, Math.max(map.get(i + 1), nums[i] + map.get(i + 2)));
    }

    return map.get(0);
}

console.log(rob3(nums));

// 发现状态转移只和dp[i]最近的两个状态有关，可以进一步优化，将空间复杂度由O(N)变为O(1)
function rob4(nums) {
    const n = nums.length;
    let dpi1 = 0;
    let dpi2 = 0;
    let dpi = 0;

    for (let i = n - 1; i >= 0; i--) {
        dpi = Math.max(dpi1, dpi2 + nums[i]);
        dpi2 = dpi1;
        dpi1 = dpi;
    }

    return dpi;
}

console.log(rob4(nums));

// 该问题是求最值问题，优先考虑动态规划
// 动态规划问题首先考虑是否具备最优子结构，只有具备最优子结构才能够使用动态规划
// 1. 状态和选择
// 本问题的状态：当前房子的索引
// 选择就是：抢与不抢
// 2. dp数组含义
// dp[i]表示从i索引开始能够在不报警前提下抢到的最多钱数
// 3. 状态转移
// 如果想求得dp[i],则nums[i]抢与不抢得到的最大值,即dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2])
// 4. base case
// 当i === nums.length || i === nums.length + 1时，结果为0

function rob5(nums) {
    const dp = (new Array(nums.length + 2)).fill(0);

    // 遍历数组
    for (let i = nums.length - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]);
    }

    return dp[0];
}

console.log(rob5(nums));

使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

// 最值问题优先考虑动态规划
// 1. 状态和选择
// 状态：阶数
// 选择：跳1台阶或2台阶
// 2. dp数组函数
// 达到n台阶所需要的最小费用
// 3. 状态转移逻辑
// dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
// 4. base case
// dp[0] = 0;
// dp[1] = 0;
// dp[2] = Math.min(cost[0], cost[1])
function minCostClimbingStairs(cost) {
    const n = cost.length;
    const dp = (new Array(n + 1)).fill(0);

    // base case
    dp[2] = Math.min(cost[0], cost[1]);

    // 循环
    for (let i = 3; i < dp.length; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    return dp[n];
}

const cost = [10,15,20];
console.log(minCostClimbingStairs(cost));

不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3 输出：5

// 二叉树问题
// 考虑遍历一遍二叉树或递归
function numTrees(n) {
    // 为了解决子问题重复问题，引入备忘录
    const memo = [];
    for (let i = 0; i <= n; i++) {
        memo.push([]);
        for (let j = 0; j <= n; j++) {
            memo[i].push(0);
        }
    }
    // 递归获取结果
    const count = (low, high) => {
        // 递归终止条件
        if (low > high) {
            return 1;
        }

        if (memo[low][high] > 0) {
            return memo[low][high];
        }

        let result = 0;

        for (let i = low; i <= high; i++) {
            result += count(low, i - 1) * count(i + 1, high);
        }

        memo[low][high] = result;
        return result;
    };

    return count(1, n);
}

console.log(numTrees(3));