动态规划

动态规划这个问题，我在当初算法课的时候，是有了一点简单的了解，就针对包裹取物之类的问题的讨论，但是好像转换题目后发现对转移方程的问题，一直没用系统的总结，今天就抽出一天时间来处理动态规划的问题吧。

参考了网上的问题，有一句话我很赞同，动态规划的一般形式就是求最值。是运筹学中的一种优化方案，一般求最值，肯定是要穷举所有的情况的，但是动态规划有一点特别，特别的是在求解问题的时候，会有很多的重叠子问题，暴力破解就会是指数级的复杂度，因此我们需要引入DP表来优化问题。避免不必要的计算。

1.斐波那契数列

为什么要从简单的问题入手，简单的问题，你才有精力集中在算法的通用思想上，而不会被隐晦的细节搞的莫名其妙。

1
2
3
4
int fib(int N){
	if(N==1 || N==2) return 1;
	return fib(N - 1) + fib(N - 2);
}

这是我们刚开始接触递归时候的经典写法，但是这个写法很低效，我们来思考一下，f(20)要求f(19)+f(18),f(19)=f(18)+f(17),那么光f(18)就计算了两次，那f(17)就会出现3次，再往下就会不断的重复计算。到f(3)岂不是要重复很多次。那么我们来优化一下重叠子问题的问题。

1
2
3
4
5
6
7
8
9
10
11
12
int fib(int N){
	if(N < 1) return 0;
	vector<int> dp(N+1, 0);
	return helper(dp, N);
}

int helper(vector<int>& dp, int n){
	if(n == 1 || n==2) return 1;	//base case
	if(dp[n] != 0) return dp[n];
	dp[n] = helper(dp,n-1) + helper(dp,n-2);
	return dp[n];
}

实际上带着备忘录的递归解法的效率已经和动态规划差不多了。不过这种方式是自顶向下s的，动态规划是自底向上的。

1
2
3
4
5
6
7
8
9
10
11
12
int fib(int N){
	if(N < 1) return 0;
	if(N == 1 || N == 2) return 1;
	vector<int> dp(N+1,0);
    //base case
    dp[1] = dp[2] = 1;
    for(int i = 3;i <= N; i++)
    {
        dp[i] = dp[i-1] +dp[i-2]
}
    return dp[N];
}

甚至还能更优化，你会发现，有时候只需要两个前元素，就能完成计算，甚至能把空间复杂度给优化到o(1)。

2、最长公共子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function LCS(str1, str2) {
    if (str1 === "" || str2 === "") {
     return "";
    }
    var len1 = str1.length;
    var len2 = str2.length;
    var a = new Array(len1);
    var maxLen = 0;
    var maxPos = 0;
    for (var i = 0; i < len1; i++) { 
     for (var j = len2 - 1; j >= 0; j--) {
      if (str1.charAt(j) == str2.charAt(i)) {
       if (i === 0 || j === 0) {
        a[j] = 1;
       } else {
        a[j] = a[j - 1] + 1;
       }
      } else {
       a[j] = 0;
      }
      if (a[j] > maxLen) {
       maxLen = a[j];	//最大匹配长度
       maxPos = j;		//最长匹配的点是末尾
      }
     }
    }
    return str1.substr(maxPos - maxLen + 1, maxLen);
   }

该问题分解成最小子问题，是两个字符的比较，两重for循环，将db table绘制出来，如果相等，则该点的匹配长度为前一字符的匹配长度加1，如果该匹配点为开头第一个点，则匹配长度为1。

参考链接：https://www.jb51.net/article/134330.htm

3、子数组的最大累加问题

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

[要求]时间复杂度为O(n)，空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function maxsum(arr) {
    if(arr.length === 0)
    return 0;
    let cur = 0;
    let len = arr.length;
    let max = 0;
    for(let i = 0;i < len;i++){
        cur += arr[i];
        max = Math.max(cur,max);
        cur = cur>0?cur:0;
    }
    return max;
}
let arr = [1, -2, 3, 5, -2, 6, -1]
console.log(maxsum(arr))

这道题只遍历一遍，逐步累加，如果相加的过程中出现负值，则直接抛弃，因为如果是负值起步，不可能是最大值了，非负就一直加下去。

4、机器人寻路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
    function getsum(x){  //求和
        let sum = 0;
        while(x){
            sum += x%10;
            x = Math.floor(x/10)
        }
        return sum;
    }
    const directionAry = [
       [1,0],
       [0,1]
    ]
    let arrived = new Set(['0,0'])
    let queue = [[0,0]];
    while(queue.length){
        let [x,y] = queue.shift();
        for(let i = 0 ;i < 2;i++){
            let offsetX = x + directionAry[i][0];
            let offsetY = y + directionAry[i][1];
            if(offsetX < 0 || offsetX >= m ||offsetY < 0 ||offsetY >= n || getsum(offsetX)+getsum(offsetY)>k||arrived.has(`${offsetX},${offsetY}`))
            {
                continue;
            }
            arrived.add(`${offsetX},${offsetY}`);
            queue.push([offsetX,offsetY]);
        }
    } 
    return arrived.size;
}
console.log(movingCount(1,2,1))
5、矩阵中的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    let row = board.length;
    let col = board[0].length;
    let res = false;
    var dfs = function (x, y, k, board, word) {
        if (x >= row || x < 0 || y >= col || y < 0)
            return false;
        let temp = board[x][y];
        if (board[x][y] === word[k]) {
            board[x][y] = '*'
            if (word.length - 1 === k) {
                return true;
            }
            if(dfs(x + 1, y, k + 1, board, word) || dfs(x - 1, y, k + 1, board, word) || dfs(x, y + 1, k + 1, board, word) || dfs(x, y - 1, k + 1, board, word))
            return true;
            else {
                board[x][y] = temp;
                return false;
            }
        } else {
            return false;
        }
    }
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            res = word[0] === board[i][j] && dfs(i, j, 0, board, word) || res
        }
    }
    return res;
};
console.log(exist([["C", "A", "A"], ["A", "A", "A"], ["B", "C", "D"]],
    "AAB"))
6、把数字翻译成字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function (num) {
    if (num === 0) return 1;
    let str = num.toString();
    const length = str.length;
    let dp = new Array(length).fill(0);
    dp[0] = 1;
    for (let i = 1; i < length; i++) {
        let temp = Number(str[i - 1] + str[i]);
        if (10 <= temp && temp <= 25) {
            if(i>1)
            dp[i] = dp[i-1] + dp[i-2];
            else dp[i] = dp[i-1] + 1;
        }else dp[i] = dp[i-1];
    }
    return dp.pop();
};

7、礼物的最大价值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxValue = function(grid) {
    const rowNum = grid.length;
    const colNum = grid[0].length;
    const dp = [];
    for (let i = 0; i < rowNum; ++i) {
        dp[i] = [];
        for (let j = 0; j < colNum; ++j) {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = grid[0][0];
    for (let i = 1; i < rowNum; ++i) {
        dp[i][0] = grid[i][0] + dp[i - 1][0];
    }

    for (let j = 1; j < colNum; ++j) {
        dp[0][j] = grid[0][j] + dp[0][j - 1];
    }

    for (let i = 1; i < rowNum; ++i) {
        for (let j = 1; j < colNum; ++j) {
            dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[rowNum - 1][colNum - 1];
};

其他：

8、字符串的排列组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
    if (!s)
        return [];
    if (s.length === 1)
        return [s];
    const res = [];
    const list = s.split('');
    let permu = function (list, begin) {
        if (begin === list.length) {
            res.push(list.join(''));
        } else {
            let set = new Set();
            for (let i = begin; i < s.length; i++) {
                if (set.has(list[i]))
                    continue;
                let temp = list[begin];
                list[begin] = list[i];
                list[i] = temp;

                permu(list, begin + 1);

                temp = list[begin];
                list[begin] = list[i];
                list[i] = temp;
                set.add(list[i]);
            }
        }
    }
    permu(list, 0);
    return res;
};

9、逆序对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    let sum = 0;
    mergeSort(nums);
    return sum;

    function mergeSort(nums) {
        if (nums.length < 2) return nums;
        const mid = parseInt(nunms.length / 2);
        let left = nums.slice(0, mid);
        let right = nums.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        let res = [];
        let leftLen = left.length;
        let rightLen = right.length;
        let len = leftLen + rightLen;
        for (let index = 0, i = 0, j = 0; index < len; index++) {
            if(i >= leftLen) res[index] = right[j++];
            else if(j>=rightLen) res[index] = left[i++];
            else if(left[i] <= right[j]) res[index] = left[i++];
            else {
                res[index] = right[j++];
                sum += leftLen - i;
            }
        }
        return res;
    }
};
10、最长回文子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(arr) {
    let left = 0;
    let right = 0;
    let max = 0;
    let now_n = 0;
    let maxstr = "";
    let max_odd = 0;
    let max_even = 0;
    let odd = false;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i - 1] === arr[i + 1]) {
            now_n = 1;
            left = i - 1;
            right = i + 1;
            max_odd = getMax(now_n, left, right, arr);
        }
        if (arr[i] === arr[i + 1]) {
            now_n = 2
            left = i - 1;
            right = i + 2;
            max_even = getMax(now_n, left, right, arr)
        }
        now_n = Math.max(max_odd, max_even)
        odd = max_odd === now_n ? true : false;
        if (now_n > max && odd) {
            max = now_n;
            maxstr = arr.substr(i - Math.floor(max - 1) / 2, max)
        } else if (now_n > max && !odd) {
            max = now_n;
            maxstr = arr.substr(i - max / 2 + 1, max)
        }
        max_even = 0;
        max_odd = 0;
    }
    if (maxstr === "") { return arr[0] } else {
        return maxstr;
    }
}
function getMax(now_n, left, right, arr) {
    while (left >= 0 && right < arr.length && arr[left] === arr[right]) {
        now_n = now_n + 2;
        left--;
        right++;
    }
    return now_n;
}
算法总结
算法总结

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！