// 遞歸的形式試試(這種形式可定不滿(mǎn)足面試官要求，從而超時(shí)，但是在這個(gè)基礎(chǔ)上可以改成備忘錄，備忘錄之后進(jìn)而改成動(dòng)態(tài)規(guī)劃)
function lengthOfLIS1(nums) {

    // 該遞歸函數(shù)表示以nums[index]結(jié)尾的部分的最長(zhǎng)遞增子序列值
    const helper = (nums, index) => {
        // 邊界條件
        if (index === 0) {
            return 1;
        }

        let result = 1;
        for (let i = 0; i < index; i++) {
            // 獲取子問(wèn)題結(jié)果
            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;

    // 因?yàn)樽铋L(zhǎng)遞增子序列有可能以任意值結(jié)果，所以遍歷一遍找到最大
    for (let i = 0; i < nums.length; i++) {
        result = Math.max(helper(nums, i), result);
    }

    return result;
}

// 備忘錄形式進(jìn)行優(yōu)化
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;
}

// 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，需要一個(gè)dp數(shù)組，假設(shè)dp[0……i-1]已經(jīng)被算出來(lái)了，然后根據(jù)這些結(jié)果算出來(lái)dp[i]

// 在該問(wèn)題中，dp數(shù)組的含義是：dp[i]表示以nums[i]這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
// 根據(jù)這個(gè)定義可以推出bad case：dp[i]初始值為1，因?yàn)橐詎ums[i]結(jié)尾的最長(zhǎng)遞增子序列起碼要包含它自己

// 如何找到動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移關(guān)系
// 1. 明確dp數(shù)組所存數(shù)據(jù)的含義
// 2. 根據(jù)dp數(shù)組的含義，運(yùn)用數(shù)學(xué)歸納法的思想，假設(shè)dp[0……i-1]都已知，想辦法求出dp[i],一旦這一步完成，整個(gè)題目基本就解決了

function lengthOfLIS3(nums) {
    // 初始化dp數(shù)組,dp[i]表示以nums[i]這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，其中最小為1
    const dp = new Array(nums.length).fill(1);

    let result = 0;
    // 遍歷一遍
    for (let i = 0; i < nums.length; i++) {
        // 要找到以i為結(jié)尾的最長(zhǎng)遞增子序列，就是前面i - 1項(xiàng)中存在的最長(zhǎng)遞增子序列 + 1，通過(guò)比較獲取其最大的
        for (let j = 0; j < i; j++) {
            // 當(dāng)nums[j]的值小于[i]的值時(shí),才滿(mǎn)足遞增子序列的要求
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        // 獲取從0-n中最長(zhǎng)的
        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));

// 既然是最值問(wèn)題，肯定優(yōu)先考慮動(dòng)態(tài)規(guī)劃
// 對(duì)于兩個(gè)字符串求子序列的問(wèn)題，都是用兩個(gè)指針i和j分別在兩個(gè)字符串上移動(dòng)，大概率是動(dòng)態(tài)規(guī)劃的思路
// 首先寫(xiě)一個(gè)dp函數(shù)：
// 定義：計(jì)算 s1[0……i] 和 s2[0……j] 的最長(zhǎng)公共子序列長(zhǎng)度
// int dp(String s1, int i, String s2, int j)
// 這個(gè)dp函數(shù)的定義是：dp(s1, i, s2, j)計(jì)算s1[0……i]和s2[0……j]的最長(zhǎng)公共子序列長(zhǎng)度。
// 根據(jù)這個(gè)定義，那么我們想要的答案就是dp(s1, s1.length, s2, s2.length)，且 base case 就是i < 0或j < 0時(shí)，因?yàn)檫@時(shí)候s1[0……i]或s2[0……j]就相當(dāng)于空串了，最長(zhǎng)公共子序列的長(zhǎng)度顯然是 0
// 如果在求dp[i][j]的時(shí)候，此時(shí)會(huì)出現(xiàn)以下幾種情況：
// 1. 如果text1[i] === text2[j],此時(shí)證明該字符在該lcs中，則dp[i][j] = dp[i - 1][j - 1] + 1;
// 2. 如果text1[i] !== text2[j],此時(shí)可能：
// （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]可以被省略,因?yàn)槎嘁粋€(gè)字符去比較肯定比少一個(gè)字符去比較結(jié)果長(zhǎng)

// 暴力遞歸
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) {
    // 用一個(gè)二維數(shù)組去存儲(chǔ)對(duì)應(yīng)的結(jié)果值，在遞歸的時(shí)候首先判斷是否存在這樣的結(jié)果，有的話直接返回
}

// 改成動(dòng)態(tài)規(guī)劃的形式
// 首先判斷是否具備最優(yōu)子結(jié)構(gòu)，只有具備最優(yōu)子結(jié)構(gòu)，才能通過(guò)子問(wèn)題得到原問(wèn)題的最值
// 緊接著找到正確的狀態(tài)轉(zhuǎn)移方程
// 1. 明確狀態(tài)：本題的狀態(tài)就是text1[0……i]和tex2[0……j]的最長(zhǎng)子序列
// 2. 定義dp數(shù)組/函數(shù)：dp[i][j]表示text1[0……i]和tex2[0……j]的最長(zhǎng)子序列
// 3. 明確選擇：為了獲取dp[i][j],需要指導(dǎo)dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]
// 4. 明確base case:此處的base case就是i < 0或j < 0,這個(gè)時(shí)候一個(gè)串為空，最長(zhǎng)公共子序列長(zhǎng)度就為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));

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

// 暴力遞歸方式
function rob1(nums) {
    const dp = (nums, start) => {
        // 設(shè)定遞歸結(jié)束條件
        if (start >= nums.length) {
            return 0;
        }

        // dp(nums, start + 1)表示不搶?zhuān)ハ乱患?        // nums[start] + dp(nums, start + 2)表示搶?zhuān)ハ孪录?        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));

// 動(dòng)態(tài)規(guī)劃
function rob3(nums) {
    const n = nums.length;
    const map = new Map();

    // 當(dāng)超出房間后，搶到的都為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));

// 發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移只和dp[i]最近的兩個(gè)狀態(tài)有關(guān)，可以進(jìn)一步優(yōu)化，將空間復(fù)雜度由O(N)變?yōu)镺(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));

// 該問(wèn)題是求最值問(wèn)題，優(yōu)先考慮動(dòng)態(tài)規(guī)劃
// 動(dòng)態(tài)規(guī)劃問(wèn)題首先考慮是否具備最優(yōu)子結(jié)構(gòu)，只有具備最優(yōu)子結(jié)構(gòu)才能夠使用動(dòng)態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 本問(wèn)題的狀態(tài)：當(dāng)前房子的索引
// 選擇就是：搶與不搶
// 2. dp數(shù)組含義
// dp[i]表示從i索引開(kāi)始能夠在不報(bào)警前提下?lián)尩降淖疃噱X(qián)數(shù)
// 3. 狀態(tài)轉(zhuǎn)移
// 如果想求得dp[i],則nums[i]搶與不搶得到的最大值,即dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2])
// 4. base case
// 當(dāng)i === nums.length || i === nums.length + 1時(shí)，結(jié)果為0

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

    // 遍歷數(shù)組
    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));

// 最值問(wèn)題優(yōu)先考慮動(dòng)態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 狀態(tài)：階數(shù)
// 選擇：跳1臺(tái)階或2臺(tái)階
// 2. dp數(shù)組函數(shù)
// 達(dá)到n臺(tái)階所需要的最小費(fèi)用
// 3. 狀態(tài)轉(zhuǎn)移邏輯
// 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]);

    // 循環(huán)
    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));

// 二叉樹(shù)問(wèn)題
// 考慮遍歷一遍二叉樹(shù)或遞歸
function numTrees(n) {
    // 為了解決子問(wèn)題重復(fù)問(wèn)題，引入備忘錄
    const memo = [];
    for (let i = 0; i <= n; i++) {
        memo.push([]);
        for (let j = 0; j <= n; j++) {
            memo[i].push(0);
        }
    }
    // 遞歸獲取結(jié)果
    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));