内容简介：本文主要总结了动态规划的几种经典题型，分别为经典01背包、最少硬币、最大正方形、最大加号标志。背包容量capacity=5，有三个物品(value, weight)，分别是(3,2),(4,3),(5,4)求出其搭配组合，使得背包内总价最大，且最大价值为多少？首先理清思路列出表格：
本文主要总结了动态规划的几种经典题型，分别为经典01背包、最少硬币、最大正方形、最大加号标志。
一、经典01背包
1. 题目
背包容量capacity=5，有三个物品(value, weight)，分别是(3,2),(4,3),(5,4)求出其搭配组合，使得背包内总价最大，且最大价值为多少？
2.思路
首先理清思路列出表格：
如果背包总容量为0，那么很显然地，任何物品都无法装进背包，那么背包内总价值必然是0。所以第一步先填满 j=0 的情况。
接下来将从上到下，从左往右地填写这个表格。分析第i行时，它的物品组合仅能是小于等于i的情况。所以现在把注意力定位到 i =0, j = 1 的空格上。
i=0 j=1 : 背包总容量为1，但是物品0 的重量为 2，无法装下去，所以这一格应该填 0。
i=0 j=2 : 背包总容量为2，刚好可以装下物品0 ，由于物品0 的价值为3，因此这一格填 3。
后面同理。
i=1 j=1 : 背包总容量为1，但是物品0 的重量为 2，物品1重量为3，背包无法装下任何物品，所以填 0。
| val | weight | j=0 | j=1 | j=2 | j=3 | j=4 | j=5 | |
|---|---|---|---|---|---|---|---|---|
| i=0 | 3 | 2 | 0 | 0 | 3 | 3 | 3 | 3 |
| i=1 | 4 | 3 | 0 | 0 | 3 | 4 | 4 | 7 |
| i=2 | 5 | 4 | 0 | 0 | 3 | 4 | 5 | 7 |
伪代码：
if(j>w[i]){
T[i][j] = T[i-1][j]
}else{
T[i][j] = max(T[i-1][j-w[i]]+val[i], T[i-1][j])
}
3.代码
function backpack(w,val,capacity,n){
var T = []
for(let i = 0;i < n;i++){
T[i] = [];
for(let j=0;j <= capacity;j++){
if(j === 0){ //容量为0
T[i][j] = 0;
continue;
}
if(j < w[i]){ //容量小于物品重量，本行hold不住
if(i === 0){
T[i][j] = 0; // i = 0时，不存在i-1，所以T[i][j]取0
}else{
T[i][j] = T[i-1][j]; //容量小于物品重量，参照上一行
}
continue;
}
if(i === 0){
T[i][j] = val[i]; //第0行，不存在 i-1, 最多只能放这一行的那一个物品
}else{
T[i][j] = Math.max(val[i] + T[i-1][j-w[i]],T[i-1][j]);
}
}
}
findValue(w,val,capacity,n,T);
return T;
}
//找到需要的物品
function findValue(w,val,capacity,n,T){
var i = n-1, j = capacity;
while ( i > 0 && j > 0 ){
if(T[i][j] != T[i-1][j]){
console.log('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]);
j = j- w[i];
i--;
}else{
i--; //如果相等，那么就到 i-1 行
}
}
if(i == 0 ){
if(T[i][j] != 0){ //那么第一行的物品也可以取
console.log('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]);
}
}
}
var values = [3,4,5],
weights = [2,3,4],
capacity = 5,
n = values.length;
console.log(backpack(weights,values,capacity,n));
二、最少硬币
1. 题目
4种硬币 1分、2分、5分、6分
总共需要11分，求最少的硬币数以及组合
2.思路
首先理清思路列出表格：
与经典背包相同，填写第i行表示只能用i和比i小的硬币。硬币数组coins[]，需要的钱数j。
当我们只能使用面额为1分的硬币时，根据上面的规则，那么很显然，总额为几分，就需要几个硬币。
当我们有1分和2分两种面额时，那么组合方式就相对多了点。
i=1 j = 1：总额为1时，只能使用1分的面额。即填1。
i=1 j = 2：总额为2时，可以使用2个1分的，也可以使用1个2分的。
因为我们要求最少硬币，所以使用1个2分的。表格里填1。
以此类推：
| j=0 | j=1 | j=2 | j=3 | j=4 | j=5 | j=6 | j=7 | j=8 | j=9 | j=10 | j=11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| i=0 1分 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| i=1 2分 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
| i=2 5分 | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
| i=3 6分 | 0 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 3 | 3 | 2 |
伪代码：
if(j<coins[i]){
T[i][j] = T[i-1][j]
}else{
T[i][j] = min(T[i-1][j], T[i][j-coins[i]]+1)
}
3.代码
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
coins.sort((a,b)=>(a-b));
var T = [];
for(let i=0; i<coins.length; i++){
T[i] = [];
for(let j=0; j<=amount; j++){
T[i][j] = 0;
}
}
for(let i=0; i<T.length; i++){
for(let j=0; j<T[i].length; j++){
if(j==0){
T[i][j] = 0;
continue;
}
if(i==0){
if(Number.isInteger(j/coins[i])){
T[i][j] = j/coins[i];
}else{
T[i][j] = Infinity;
}
}else{
if(j<coins[i]){
T[i][j] = T[i-1][j];
}else{
T[i][j] = Math.min(T[i-1][j], T[i][j-coins[i]]+1);
}
}
}
}
return T[T.length-1][T[0].length-1]===Infinity?-1:T[T.length-1][T[0].length-1];
};
三、最大正方形
1. 题目
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
2.思路
首先用例中不一定会给正方形，也可能是长方形，所以必须分别求长和宽。
其次如果此点的值是0，则直接将结果设为0；如果此点的值为1，则它等于它左方、上方、左上方三者的最小值+1。
最后是需要一个变量max，在遍历的过程中不断修改自身获取dp中的最大值。
3.代码
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalSquare = function(matrix) {
let len1 = matrix.length, len2;
var dp = new Array(len1);//设置长度
let max = 0;//记录矩阵中最大值
for(let i=0; i<len1; i++){
len2 = matrix[i].length;
dp[i] = new Array(len2);
}
for(let i=0; i<len1; i++){
for(let j=0; j<len2; j++){
if(i==0 || j==0){
dp[i][j] = matrix[i][j] == '1'?1:0;
}else{
dp[i][j] = matrix[i][j] == '1'? (Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1):0;
}
max = Math.max(max, dp[i][j]);
}
}
return max*max;
};
四、最大加号标志
1. 题目
在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。
一个 k” 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k” 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。
k 阶轴对称加号标志示例:
阶 1:
000
010
000
阶 2:
00000
00100
01110
00100
00000
阶 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
示例 1：
输入: N = 5, mines = [[4, 2]]
输出: 2
解释:
11111
11111
11111
11111
11011
在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。
示例 2：
输入: N = 2, mines = []
输出: 1
解释:
11
11
没有 2 阶加号标志，有 1 阶加号标志。
示例 3：
输入: N = 1, mines = [[0, 0]]
输出: 0
解释:
0
没有加号标志，返回 0 。
2.思路
首先要给所有位置设置最大值即边长N。
let dp = [...Array(N)].map(() => Array(N).fill(N));
循环遍历所有行，从四个方向更新dp。
for(let i=0; i<N; i++){
for(let l=0, left=0; l<N; l++){
dp[i][l] = Math.min(dp[i][l], left = (dp[i][l] == 0 ? 0: left+1));
}
for(let r=N-1, right=0; r>=0; r--){
dp[i][r] = Math.min(dp[i][r], right = (dp[i][r] == 0 ? 0: right+1));
}
for(let u=0, up=0; u<N; u++){
dp[u][i] = Math.min(dp[u][i], up = (dp[u][i] == 0 ? 0: up+1));
}
for(let d=N-1, down=0; d>=0; d--){
dp[d][i] = Math.min(dp[d][i], down = (dp[d][i] == 0 ? 0: down+1));
}
}
left right up down注意每遍历一行都要更新为0。
3.代码
/**
* @param {number} N
* @param {number[][]} mines
* @return {number}
*/
var orderOfLargestPlusSign = function(N, mines) {
let dp = [...Array(N)].map(() => Array(N).fill(N));
for(let i=0; i<mines.length; i++){
dp[mines[i][0]][mines[i][1]] = 0;
}
let left, right, up, down;
for(let i=0; i<N; i++){
for(let l=0, left=0; l<N; l++){
dp[i][l] = Math.min(dp[i][l], left = (dp[i][l] == 0 ? 0: left+1));
}
for(let r=N-1, right=0; r>=0; r--){
dp[i][r] = Math.min(dp[i][r], right = (dp[i][r] == 0 ? 0: right+1));
}
for(let u=0, up=0; u<N; u++){
dp[u][i] = Math.min(dp[u][i], up = (dp[u][i] == 0 ? 0: up+1));
}
for(let d=N-1, down=0; d>=0; d--){
dp[d][i] = Math.min(dp[d][i], down = (dp[d][i] == 0 ? 0: down+1));
}
}
var max = 0;
for(let i=0; i<N; i++){
for(let j=0; j<N; j++){
max = Math.max(max, dp[i][j]);
}
}
return max;
};
总结：
本文主要对动态规划几种经典题做了简单介绍，希望对大家对算法方面的学习有所帮助，总结不到位的地方还请大家批评指正。
友情参考链接：
https://juejin.im/post/5affed3951882567161ad511
https://juejin.im/post/5b0a8e0f51882538b2592963
https://leetcode-cn.com/problemset/all/以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
计算机组成（第 6 版）
Andrew S. Tanenbaum、Todd Austin / 刘卫东、宋佳兴 / 机械工业出版社 / 2014-8-19 / CNY 99.00
本书采用结构化方法来介绍计算机系统，书的内容完全建立在“计算机是由层次结构组成的，每层完成规定的功能”这一概念之上。作者对本版进行了彻底的更新，以反映当今最重要的计算机技术以及计算机组成和体系结构方面的最新进展。书中详细讨论了数字逻辑层、微体系结构层、指令系统层、操作系统层和汇编语言层，并涵盖了并行体系结构的内容，而且每一章结尾都配有丰富的习题。本书适合作为计算机专业本科生计算机组成与结构课程的教......一起来看看 《计算机组成（第 6 版）》 这本书的介绍吧!
