【校招VIP】前端算法考察之动态规划

发布于:2023-01-22 ⋅ 阅读:(2) ⋅ 点赞:(0) ⋅ 评论:(0)

考点介绍:

动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。动态规划可以通过填表的方式来逐步推进,得到最优解。

本期分享的前端算法考察之动态规划,分为试题、文章以及视频三部分。

答案详情解析和文章内容点击下方链接即可查看!

一、考点题目

1、最优二叉搜索树问题的动态规划算法(设函数名 binarysearchtree)

解答:

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

void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w)

  

{

  

int i,j,k,t,l;

  

for(i=1;i<=n+1;i++)

  

{

  

w[i][i-1]=a[i-1];

  

m[i][i-1]=0;

  

}

  

for(l=0;l<=n-1;l++)//----l 是下标 j-i 的差

  

for(i=1;i<=n-l;i++)

  

{

  

j=i+l;

  

w[i][j]=w[i][j-1]+a[j]+b[j];

  

m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];

  

s[i][j]=i;

  

for(k=i+1;k<=j;k++)

  

{

  

t=m[i][k-1]+m[k+1][j]+w[i][j];

  

if(t<m[i][j])

  

{

  

m[i][j]=t;

  

s[i][j]=k;

  

}

  

}

  

}

  

}

2、给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

解答:运用的是动态规划的思想,由于是求最长回文字符串......

3、(120三角形最小路径和) 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

解答:相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点......

4、小区成二叉树结构,如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

解答:选择二叉树中不相邻的节点,使得节点之和为最大......

二、考点文章

1、动态规划算法

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法……

2、JavaScript算法之动态规划

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程……

3、【校招VIP】动态规划的简单理解及例子

动态规划是分治的延伸,通俗一点来说就是大事化小,小事化无的艺术,在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果……

三、考点视频

1、前端校招的特点、考点和职业发展

前端是IT校招中目前性价比最高的职位,对所学专业要求不高,考点难度较小,且需求量大……

更多资讯可搜索校招VIP小程序查看哦!
移动端链接:https://m.xiaozhao.vip/dTopic/detail/573