
数据结构和算法—动态规划
我一直最想做的就是机器学习,所以也都是在报机器学习的岗位,在BAT三家公司中,其实还是要讲百度吧,因为阿里在一面的时候就挂了,给我的理由是我投错了岗位(据面试官讲我应该去投算法岗,但我投的是数据挖掘),后来我在想,其实还就是我没能达到她的语气要求;腾讯就别讲了,连面试都没收到(据说这个岗位不招我们学校的),这可能就是个猜测吧。重点说说百度的笔试和面试吧,单纯从技术上来讲,因为我在做机器学习嘛,百度还是我最心仪的公司。这次百度的招聘分为笔试+面试(三个技术面+Hr面),我挂在了最后一个技术面上,先来说说武汉的笔试吧,当然笔试题我做得还是蛮开心的,因为最后一道证明题可以说还是我平时的强项吧,面试中,前两面都还好,面得比较基础,包括基本的数据结构,算法,然后是机器学习的算法理解,不同算法之间的对比,这也正是我平时做的一些工作,这样的过程还是蛮舒服的,整个流程下来,我觉得问题不是很大。最后一关就是很多实际的项目问题,由于我自己平时项目较少,加之自己的导师不是做机器学习的,没做过具体的机器学习相关项目,只是将算法学习的比较全。
我写以上的东西也是给找工作的朋友一个建议,也是给自己一个醒目的教训,多去实践,所以这段时间我还是会努力更新我的博客,当然不完全是前面的机器学习算法,现在将包括更多的东西,我会把我现在在做的项目也慢慢更新上来,然后又基本的算法的学习材料,希望关注我博客的朋友,大家一起努力,我不是科班出身,但是我希望大家不吝赐教,有你的帮助我会成长的更快。
好了,就写到这吧。我想还是从一些算法开始入手吧,今天还是来更新一篇动态规划的文章。
一、动态规划的思想
动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行求解,最终得到整个问题的解。有人在想这样的方式和分治法的求解很像。
动态规划:各个子问题不是独立的,他们包含了公共子问题
分治法:一个大问题是被划分成一些独立的子问题,通过递归地求解子问题最终得到整个问题的解
在动态规划法中,与其对交叠的子问题一次一次求解,不如对每个较小的子问题只求解一次并把结果记录在表中,这样就能从表中得到原始问题的解。举个简单的例子,对于菲波那切数列来说:
对于这样的递推式,可以把一个复杂的问题分解成几个非独立的子问题,我们可以采用的方式是记录每一组值,如斐波那契数列的值依次是0,1,1,2,3,5,...。而不需要重复去计算。
二、用动态规划求解二项式系数
二项式系数问题是一个求解的问题。我们有如下的递推式:
要计算的值,我们需要记录
到
之间的值。动态规划的核心思想就是要找到这样的递推式,然后构建这样的存储空间去记录中间的值,避免重复计算。最简单的方式是利用数组去记录。数据分析师培训
如上的问题可以用下面的Java代码实现:
[java] view plain copy 在CODE上查看代码片派生到我的代码片
package org.algorithm.dynamicprogramming;
/**
* 利用动态规划的思想去求解二项式系数的问题
*
* @author dell
*
*/
public class CalculateDemo {
/**
* 用动态规划计算C(n,k)
*
* @param n为二项式的参数
* @param k为二项式的参数
* @return C(n,k)的值
*/
public static int calBinomial(int n, int k) {
int C[][] = new int[n+1][k+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= minValue(i, k); j++) {
if (j == 0 || j == i) {
C[i][j] = 1;
} else {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
}
return C[n][k];
}
// 返回较小的值
public static int minValue(int i, int k) {
return (i <= k ? i : k);
}
public static void main(String args[]) {
int n = 10;
int k = 5;
System.out.println(calBinomial(n, k));
}
}
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
SQL Server 中 CONVERT 函数的日期转换:从基础用法到实战优化 在 SQL Server 的数据处理中,日期格式转换是高频需求 —— 无论 ...
2025-09-18MySQL 大表拆分与关联查询效率:打破 “拆分必慢” 的认知误区 在 MySQL 数据库管理中,“大表” 始终是性能优化绕不开的话题。 ...
2025-09-18CDA 数据分析师:表结构数据 “获取 - 加工 - 使用” 全流程的赋能者 表结构数据(如数据库表、Excel 表、CSV 文件)是企业数字 ...
2025-09-18DSGE 模型中的 Et:理性预期算子的内涵、作用与应用解析 动态随机一般均衡(Dynamic Stochastic General Equilibrium, DSGE)模 ...
2025-09-17Python 提取 TIF 中地名的完整指南 一、先明确:TIF 中的地名有哪两种存在形式? 在开始提取前,需先判断 TIF 文件的类型 —— ...
2025-09-17CDA 数据分析师:解锁表结构数据特征价值的专业核心 表结构数据(以 “行 - 列” 规范存储的结构化数据,如数据库表、Excel 表、 ...
2025-09-17Excel 导入数据含缺失值?详解 dropna 函数的功能与实战应用 在用 Python(如 pandas 库)处理 Excel 数据时,“缺失值” 是高频 ...
2025-09-16深入解析卡方检验与 t 检验:差异、适用场景与实践应用 在数据分析与统计学领域,假设检验是验证研究假设、判断数据差异是否 “ ...
2025-09-16CDA 数据分析师:掌控表格结构数据全功能周期的专业操盘手 表格结构数据(以 “行 - 列” 存储的结构化数据,如 Excel 表、数据 ...
2025-09-16MySQL 执行计划中 rows 数量的准确性解析:原理、影响因素与优化 在 MySQL SQL 调优中,EXPLAIN执行计划是核心工具,而其中的row ...
2025-09-15解析 Python 中 Response 对象的 text 与 content:区别、场景与实践指南 在 Python 进行 HTTP 网络请求开发时(如使用requests ...
2025-09-15CDA 数据分析师:激活表格结构数据价值的核心操盘手 表格结构数据(如 Excel 表格、数据库表)是企业最基础、最核心的数据形态 ...
2025-09-15Python HTTP 请求工具对比:urllib.request 与 requests 的核心差异与选择指南 在 Python 处理 HTTP 请求(如接口调用、数据爬取 ...
2025-09-12解决 pd.read_csv 读取长浮点数据的科学计数法问题 为帮助 Python 数据从业者解决pd.read_csv读取长浮点数据时的科学计数法问题 ...
2025-09-12CDA 数据分析师:业务数据分析步骤的落地者与价值优化者 业务数据分析是企业解决日常运营问题、提升执行效率的核心手段,其价值 ...
2025-09-12用 SQL 验证业务逻辑:从规则拆解到数据把关的实战指南 在业务系统落地过程中,“业务逻辑” 是连接 “需求设计” 与 “用户体验 ...
2025-09-11塔吉特百货孕妇营销案例:数据驱动下的精准零售革命与启示 在零售行业 “流量红利见顶” 的当下,精准营销成为企业突围的核心方 ...
2025-09-11CDA 数据分析师与战略 / 业务数据分析:概念辨析与协同价值 在数据驱动决策的体系中,“战略数据分析”“业务数据分析” 是企业 ...
2025-09-11Excel 数据聚类分析:从操作实践到业务价值挖掘 在数据分析场景中,聚类分析作为 “无监督分组” 的核心工具,能从杂乱数据中挖 ...
2025-09-10统计模型的核心目的:从数据解读到决策支撑的价值导向 统计模型作为数据分析的核心工具,并非简单的 “公式堆砌”,而是围绕特定 ...
2025-09-10