牛客844784119号

分类

图(1) 总结(9) 经典题型(4)

/ 注册

全部文章（共5篇）

动态规划解题一般思路

虽然动归没有确切的解题思路，可是以下的步骤却是常用的： 1.将原问题分解，缩小成为子问题.（与原题形式相同，不过规模变小）（例如数字三角形的子问题是求从倒数第二层走到倒数第一层时的最大值）将子问题不断化简，得出答案，当子问题可以完美解决，原问题便可完美解决。 2.设计该题的状态.一个状态的好坏直接影...

动态规划

2020-02-08

0 586

最长公共子序列（LCS）

1.最长公共子序列的定义：我们称序列Z=<z1,z2,...,zk>，Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>X=<x1,x2,...,xm>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik>&...

动态规划

2020-02-07

1 980

最长不下降子序列（LIS）

一：最长不下降子序列状态转移方程： f[i]=max(f[(0--i-1)]+1,f[i]) //f[i]指以i结尾的的最长不下降子序列的最长长度二:具体思路: 正确思路...

动态规划

2020-01-28

1 769

01背包详解

一.01背包状态转移方程解析：原方程 f(i,j)=max(f(i-1,j),f(i-1,j-w[i])+c[i]))1.f(i,j)表示前i件物品放到容积为j的背包中的最大价值，w[i]表示第i件物品的重量，c[i]表示第i件物品的价值 2.一件物...

动态规划

2020-01-26

1 523

数字三角形详解

数字三角形状态转移方程(由底层向顶层)： a[i][j]=max(a[i+1][j+1],a[i+1][j])+a[i][j]（数组a为输入存储数组，n为层数，同时也是列数，a[i][j]表示该点到底层的最大权值之和（即最长路径））...

动态规划

2020-01-17

2 439