# Javascript数据结构与算法之动态规划

# 动态规划的定义

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

使用动态规划设计的算法从它能解决的最简单的子问题开始，继而通过得到的解，去解决其他更复杂的子问题，直到整个问题都被解决。所有子问题的解通常被存储在一个数组里以便于访问。

# 动态规划的应用练习

leetcode题目练习：

斐波那契数列【简单】
最长公共子序列【中等】
比特位计数【中等】

# 1. 斐波那契数列

# 题目描述：

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

# 示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

# 示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

# 示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

# 提示：

0 ≤ N ≤ 30

# 解题思路：

预条件：F(0) = 0, F(1) = 1;
定义初始值[0,1]
从2开始循环到N，每一项都是前两项的和。
返回最后一个元素

代码实现：

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    let t = [0,1];
    for(let i = 2; i <= N; i++) {
        t[i] = t[i-1] + t[i-2];
    }
    
    return t[N];
};

# 2. 最长公共子序列

# 题目描述：

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

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

# 示例 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 <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。

# 解题思路：

初始化m+1行n+1列的二维数组
值相等+1 否则赋值左/上较大值

	a	b	c	d	e
"	0	0	0	0	0
a	1	1	1	1	1
c	1	1	2	2	2
E	1	1	2	2	3

代码实现：

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let m = text1.length, n = text2.length;
    // 初始化m+1行n+1列的二维数组
    let dp = [...Array(m + 1)].map(() => [...Array(n + 1).fill(0)]);
    for(let i = 1; i <= m; ++i) {
        for(let j = 1; j <= n; ++j) {
            if(text1[i - 1] === text2[j - 1]) { // 对角线值+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[m][n];
};

# 3. 在排序数组中查找元素的第一个和最后一个位置

# 题目描述：

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

# 示例 1:

输入: 2
输出: [0,1,1]

# 示例 2:

输入: 5
输出: [0,1,1,2,1,2]

# 进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？要求算法的空间复杂度为O(n)。你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

# 解题思路：

初始化num+1长度的dp
每一段长度在前面的值里面都算过了比如dp[5] = dp[4] + dp[1];
return dp;

代码实现：

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
    let dp = new Array(num + 1).fill(0), index = 0;
    for(let i = 1; i <= num; i++) {
        let t = Math.log2(i);
        if(parseInt(t) === t) { // 比特只有1位
            index++;
            dp[i] = 1;
        } else {
            dp[i] = dp[i - Math.pow(2, index - 1)] + 1;
        }
    }
    return dp;
};

← Javascript数据结构与算法之贪心算法 Javascript单例模式 →