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

发布于：2023-01-22 ⋅ 阅读:(171) ⋅ 点赞:(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

 

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布