动态规划实例_动态规划的案例

引入——fibonaci

// fibonaci
// 记录状态的递归，减少重复计算
function fibonaci(n) {
    let array = new Array(n).fill(0);

    function digui(n) {
        if (n == 1 || n == 2) {
            return 1;
        } else if (array[n]) {
            return array[n];
        } else {
            array[n] = digui(n-1) + digui(n-2);
            return array[n];
        }
    }
    var result = digui(n);
    console.log(result);
}

// 自底向上
function fibonaci(n) {
    let array = [1, 1];
    if ( n <= 2) {
        return 1;
    } else {
        let i = 2;
        while(i < n) {
            array[i] = array[i-1] + array[i-2];
            i++;
        }
        console.log(array[n-1]);
    }

}

// fibonaci(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

偷盗问题

// 偷盗问题
// 递归
function getCountMore(arr) {
    if (arr.length === 1) {
        return arr[0];
    } else if (arr.length === 2) {
        return Math.max(arr[0], arr[1]);
    } else {
        let len = arr.length - 1;
        return Math.max(getCountMore(arr.slice(0, len)), getCountMore(arr.slice(0, len - 1)) + arr[len]);
    }
}
// 动态规划
function getCountMore1(arr) {
    var newArr = new Array(arr.length).fill(0);
    let i = 0;
    while(i < arr.length) {
        i == 0 ? newArr[i] = arr[0] : i == 1 ? newArr[1] = Math.max(arr[0], arr[1]) :
        newArr[i] = Math.max(newArr[i-1], newArr[i-2]+arr[i]);
        i++;
    }
    console.log(newArr[arr.length - 1]);
    return newArr[arr.length - 1];
}

var result = getCountMore([1,20, 4, 50, 60])
console.log(result);

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 gift(arr) {
    let m = 0, n = 0;
    let db = [arr[m][n]];
    while(m+1 < arr.length && n+1 < arr[0].length) {
        if (arr[m][n+1] && arr[m+1] && arr[m+1][n]) {
            db.push(Math.max(arr[m][n+1], arr[m+1][n]));
            db[db.length-1] == arr[m][n+1] ? n++ : m++;
        } else {
            arr[m+1] && arr[m+1][n] ? (db.push(arr[m+1][n]),m++) : null;
            arr[m][n+1] ? db.push(arr[m][n+1], n++) : null;
        }
    }
    while (m+1 < arr.length) {
        db.push(arr[m+1][n]);
        m++;
    }
    while (n+1 < arr.length) {
        db.push(arr[m][n+1]);
        n++;
    }
    console.log(db);
    return db.reduce((a, b) => {return a + b});
}

// 标准动态规划
function gift(grid) {
    let m = grid.length, n = grid[0].length;
    let i = 0, j = 0;
    let db = [...grid];
    // 第一行 第一列的db数组
    while (i+1 < m) {
        db[i+1][j] = db[i+1][j] + db[i][j];
        i++;
    }
    i = 0;
    while (j+1 < n) {
        db[i][j+1] = db[i][j+1] + db[i][j];
        j++;
    }
    // 中间区域db[i][j]=max(dbb[i][j-1],db[i-1][j]) + db[i][j]
    let tem1, tem2;
    for(i = 1; i < m; i++) {
        for(j = 1; j < n; j++){
            // 上面
            tem1 = db[i-1][j] + db[i][j];
            // 左
            tem2 = db[i][j-1] + db[i][j];
            db[i][j] = Math.max(tem1, tem2);
        }

    }
    return db;
    return db[m-1][n-1];
}

let arr = [
    [1,3,1],
    [1,5,1],
    [4,2,1]
]
gift(arr);

// 输出路径
function path(db) {
    let m = db.length-1, n = db[0].length-1;
    let pathArr = [...Array(m+1)].map(item => {
        return Array(n+1).fill(0);
    });
    while(m > -1 && n > -1) {
        pathArr[m][n] = 1;
        if (db[m-1] && (db[m][n-1] >= db[m-1][n])) {
            n--;
        } else {
            m--;
        }
    }

    while(m > -1) {
        n = 0;
        pathArr[m][n] = 1;
        m--;
    } 
    while(n > -1) {
        m = 0;
        pathArr[m][n] = 1;
        n--;
    }
    console.log(pathArr)
    return pathArr; 
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

零钱兑换

零钱兑换
原问题：凑成总金额S所需最少的个数
子问题：凑成目标金额x(x<=S)所需最少的个数
状态：f(x)为凑成目标金额所需最少的个数
状态转移方程：
f(x-ci) 【x-ci == 0】 f(0) = 0
【x - ci < 0】 f(0) = +Infinity
f(x-ci) = min(f(x-c1), f(x-c2), f(x-c3)) + 1
f(S) = +Infinity return -1;

function coin(arr, target) {
    let dp = Array(target + 1).fill(Infinity);
    dp[0] = 0;
    // 面额
    for (let i = 1; i <= target; i++) {
        for (let j = 0; j < arr.length; j++) {
            if(i >= arr[j]) {
                dp[i] = Math.min(dp[i-arr[j]] + 1, dp[i]);
            }
        }
    }
    console.log(dp[target] == Infinity ? -1 : dp[target]);
    return dp[target] == Infinity ? -1 : dp[target];    
}
coin([1, 2, 5, 20], 11);

// 硬币组合
function num(arr, target) {
    let db = coin(arr, target);
    let result = [];
    if (db[target] == Infinity) return result;
    // 硬币剩余个数
    let temp = target;
    while(temp > 0) {
        // 存储当前的target, coin金额
        let orT = temp, index = 0, min = Infinity;
        for(let i = 0; i < arr.length; i++) {
            if(db[orT] == 1) {
                result.push(orT);
                return result;
            }
            if (min > db[temp-arr[i]]) {
                min = db[temp-arr[i]];
                temp = orT - arr[i];
                index = i;
            }
        }
        result.push(arr[index]);
    }
    if (temp < 0) return [];
    console.log(result);
    return result;
}
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

背包问题

// 背包
data = [
	{w: 1, p: 1}
]
function bag(data, w) {
    let dp = [];
    if (w <= 0) return 0;
    let len = data.length;
    let i = 0, j = 0;
    // 1件商品 第一行
    dp[0] = [];
    while (j < w) {
        j++;
        if (data[0].w <= j) {
            dp[0].push(data[0].p)
        } else {
            dp[0].push(0)
        }
    }
    // 第一列
    while (i < len - 1) {
        i++;
        dp[i] = [];
        // j = 1
        if (data[i].w <= 1) {
            dp[i].push(Math.max(dp[i - 1][0], data[i].p))
        } else {
            dp[i].push(dp[i - 1][0]);
        }
    }
    // 中间部分
    i = 1;
    while (i < len) {
        j = 1;
        while (j < w) {
            if (data[i].w > j + 1) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], data[i].p + bag(data.slice(0, i), j + 1 - data[i].w))
            }
            j++;
        }
        i++;
    }
    return dp[len - 1][w - 1]
}
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

购物单

void async function () {
    // Write your code here
    // 考虑每个物品时要考虑每种可能出现的情况，1、主件，2、主件+附件1，3、主件+附件2，4、主件+附件1+附件2，不一定每种情况都出现，只有当存在附件时才会出现对应的情况。
    const first = await readline();
    const base = 10;
    let arr = first.split(' ');
    let N = parseInt(arr[0]) / base;
    let M = parseInt(arr[1]);
    let goods = {};
    for (let i = 1; i <= M; i++) {
        let good = await readline();
        let [v, p, q] = good.split(' ').map(Number);;
        if (q) {
            goods[q] = goods[q] || []
            goods[q].push([v / base, v / base * p]);
        } else {
            goods[i] = goods[i] || []
            goods[i].unshift([v / base, v / base * p]);
        }
    }
    const dp = Array(N + 1).fill(0);

    Object.values(goods).forEach(good => {
        let v = [], w = [];
        const [first, ...rest] = good;
        v.push(first[0]);
        w.push(first[1]);
        if (rest[0]) {
            const [f1, f2] = rest;
            v.push(first[0] + f1[0]);
            w.push(first[1] + f1[1]);
            if (f2) {
                v.push(first[0] + f2[0]);
                w.push(first[1] + f2[1]);
                v.push(first[0] + f1[0] + f2[0]);
                w.push(first[1] + f1[1] + f2[1]);
            }
        }
        for (let j = N; j > -1; j--) {
            for (let s = 0; s < w.length; s++) {
                if (j - v[s] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - v[s]] + w[s])
                }
            }
        }
    })
    console.log(dp[N] * base)
}()
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

爬楼梯

机器人走格子

var uniquePaths = function(m, n) {
    let dp = [];
    let i = m - 1, j = n - 1;
    if(m == 1 || n == 1) return 1;
    // 第一列
    while(i > -1) {
        dp.push([1]);
        i--;
    } 
    // 第一行
    while(j > 0) {
        dp[0][j] = 1;
        j--;
    }
    i = 1;
    while(i < m) {
        j = 1;
        while(j < n) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
            j++;
        }
        i++;
    }
    // console.log(dp[m-1][n-1])
    return dp[m-1][n-1];
};
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

机器人走有障碍的格子

var uniquePathsWithObstacles = function(arr) {
     let m = arr.length, n = arr[0].length;
    let dp = [];
    let i = 0; j = 0;
    let temp = false;
    while(i < m) {
        if(!arr[i][0] && !temp) {
            dp.push([1]);
        } else {
            temp = true;
            dp.push([0]);
        }
        
        i++;
    } 
    temp = false;
    while(j < n) {
        if(!arr[0][j] && !temp) {
            dp[0][j] = 1;
        } else {
            dp[0][j] = 0;
            temp = true;
        }
        
        j++;
    }
    i = 1;
    while(i < m) {
        j = 1;
        while(j < n) {
            if (arr[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
            j++;
        }
        i++;
    }
    // console.log(dp[m-1][n-1])
    return dp[m-1][n-1];
};
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

扔色子的n种方法

编辑距离

// f(i,j) 代表word1的前i个字母变成word2的前j个字母最少步数
var minDistance = function(word1, word2) {
    let dp = [];
    let m = word1.length, n = word2.length;
    let i = 1, j = 0;
    if (!m || !n) return Math.max(m, n);
    // 边界条件，
    // 1. word1的第一个字母不在word2中，f(i,j) = j;
    // 2. 在，index是word1的第一个字母在word2中的位置，< index f(i,j) = j ; >= index f(i,j) = j -1;
    // 3. 第一列和第一行是一致的思想

    // 第一行
    let inside = word2.indexOf(word1[0]);
    dp[0] = [];
    if (inside == -1) {
        while(j < n) {
            j++;
            dp[0].push(j);
        }
    } else {
        while(j < n) {
            j++;
            // 注意小于等于
            if (j <= inside) {
                dp[0].push(j);
            } else {
                dp[0].push(j - 1);
            }
        }
    }
    // 第一列
    inside = word1.indexOf(word2[0]);
    if (inside == -1) {
        while(i < m) {
            i++;
            dp.push([i]);
        }
    } else {
        while(i < m) {
            i++;
            if (i <= inside) {
                dp.push([i]);
            } else {
                dp.push([i - 1]);
            }
        }
    }

    // 中间部分：min(1, 2, 3)
    // f(i-1, j-1) = a; f(i, j) = f(i-1, j-1) + (0 || 1)(取决于word1[i]==word2[j])
    // f(i-1, j) = b; f(i, j) = f(i-1, j) + 1 (删除word1[i])
    // f(i, j-1) = c; f(i, j) = f(i, j-1) + 1 (插入word2[j])

    i = 1;
    while(i < m) {
        j = 1;
        while(j < n) {
            let temp1 = dp[i-1][j-1] + (word1[i] == word2[j] ? 0 : 1);
            let temp2 = dp[i-1][j] + 1;
            let temp3 = dp[i][j-1] + 1;
            dp[i][j] = Math.min(temp1, temp2, temp3);
            j++;
        }
        i++;
    }

    console.log(dp[m-1][n-1]);
    return dp[m-1][n-1];
};

minDistance( "teacher","archer");
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

总结

动态规划是用来解决最优解的方法

四个步骤

1. 定义原问题和子问题
2. 状态（自变量）
3. 寻找状态转移方程
4. 编程实现