基础版本

[198. 打家劫舍]https://leetcode.cn/problems/house-robber/description

就是一个取或者不取的问题；只有间隔1的时候，才能取；

function rob(nums: number[]): number {
    const len = nums.length;
    if(!len) return 0;
    if(len===1) return nums[0];
    if(len===2) return Math.max(nums[0],nums[1]);
    const dp:number[] = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1])
    
    for(let i=2;i<len;i++){
        dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
    }
    
    return dp[len-1];
};

213. 打家劫舍 II

const rob1 = (nums) => {
    const len = nums.length
    if (len === 0) return 0
    if (len === 1) return nums[0]
    let dp = new Array(len+1).fill(0)
    dp[0]=nums[0]
    dp[1]= Math.max(nums[0],nums[1])
    for(let i=2;i<len;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
    }
    return dp[len-1]
}
var rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    if (n === 1) return nums[0]
    if (n === 2) return Math.max(nums[0], nums[1])
    return Math.max(rob1(nums.slice(1,n)),rob1(nums.slice(0,n-1)))
};

进阶版本

类似于01背包的，“取”或者“不取”的问题；

1143. 最长公共子序列 https://leetcode.cn/problems/longest-common-subsequence/description/

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

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

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

 

示例 1：

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

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
 

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

回溯搜索： 经典取或者不取的问题

function longestCommonSubsequence(text1: string, text2: string): number {
    const len1 = text1.length;
    const len2 = text2.length;

    const dfs = (i:number , j:number) =>{

        if(i<0 || j<0){
            return 0;
        }
        if(text1[i]===text2[j]){
            return dfs(i-1,j-1) + 1
        }else{
            return Math.max(dfs(i, j-1), dfs(i-1,j))
        }
    }
    return dfs(len1-1,len2-1);
};

记忆化搜索优化一下：

这两种方式都是从最高位往最低位计算；

function longestCommonSubsequence(text1: string, text2: string): number {

    const len1 = text1.length;
    const len2 = text2.length;

    const visited = Array.form({length: len1+1},()=> new Array(len2+1).fill(-1));

    const dfs = (i:number, j:number):number =>{
        
        if(i<0||j<0){
            return 0;
        }
        if(visited[i][j]!==-1){
            return visited[i][j]
        }
        if(text1[i]===text2[j]){
            visited[i][j] = dfs(i-1,j-1) + 1;
        }else{
            visited[i][j] = Math.max( dfs(i-1,j) , dfs(i, j-1) );
        }
        return visited[i][j]
    }
    return dfs(len1-1,len2-1)
}

换用dp的方式，从前往后面递推：

function longestCommonSubsequence(text1: string, text2: string): number {

    const len1 = text1.length;
    const len2 = text2.length;

    const dp = Array.from({length: len1+1},()=> new Array(len2+1).fill(-1));

    for(let i=0;i<len1;i++){
        for(let j=0;j<len2;j++){
            if(text1[i]===text2[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
            }else{
                dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
            }
        }
    }

    return dp[len1][len2] // 整体加1；
}