fuyuande的博客

本题在牛客网剑指offer专项里没看到，原书第二版上有，如题：这道题是开放的动态规划题，题目中只给了绳子长度，却没定义具体剪多少段，初遇此题，难以下手，看了题解，豁然开朗。设f(n)为常为n的绳子剪成m段之后可得最大值，则存在n-1中减法，得f(n) = MAX(f(i) * f(n-i))；初始值f(1),f(2),f(3)都可以计算出来，大于3则调用dp方程递归计算至n即可。思路简...

假设你正在爬楼梯。需要 n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 +...

先看题目：在一个由n个数字组成的数字串中插入r个乘号（1 <= r < n），将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。例如，对给定的数串267315682902764如何插入6个乘号，使其乘积最大？插入r个乘号是一个多阶段决策问题，应用动态规划来求解。使用动态规划需要找到状态递推关系，阶段自然就是插入的乘号了。设 f(i, k)...

先看题目：给定凸n边形P = {1，2，，，n}，每一个顶点i带一个权数r(i)(i = 1,2,,,n)。要求在该凸n边形的顶点间连n-3条互不相交的连线，把凸N边形分成n-2个三角形，每个三角形的值为其三个顶点权数之积。试确定一种三角形剖分，使得剖分的n-2个三角形的值之和最小。如下图，凸6边形，顶点序号分别为1-6，顶点的权数未在图中标出。这道题还是相当有难度的，第一次没...

这几天在学习算法方面动态规划的内容，主要是为了面试。最早接触动态规划是在大学的算法课，当时看书遇到的第一道难题就是01背包问题，自己琢磨了半天也没想出一个好的方法，看课本几行代码就搞定了，感觉特别不可思议，当时觉得算法相当强大，不过也没太花时间在这上边，最近准备大厂面试的时候，发现算法和数据结构的要求相当高，所以开始复习下算法。私以为，卓越的程序员是需要懂得算法的。在阅读内核源码的时候，经常会碰到...

先看下题目：已知14个西瓜 的重量，分别为：23 21 12 19 18 25 20 22 16 19 12 15 17 14请将这些瓜分成两堆，每堆的个数不限，使两堆西瓜重量之差最小。我们知道，动态规划类问题是存在明确的步骤的：1. 分阶段。2. 状态迁移方程。3. 求最优解。这道题要把西瓜分成两堆，假设A堆和B堆，对于每个西瓜而言，要么分到A，要么分到B，和01背...

先看下题目：给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。例如，由12个正整数组成的序列为： 48，16，45，47，52，46，36，28，46，69，14，42请在序列中删除若干项，使剩下的项为非降(即后面的项不小于前面的项)序列，剩下的非降序列最多为多少项？这道题第一次做是会做的，刷了两天动态规划类题目，第...

题目：若序列Z是序列X的子序列，又是Y的子序列，则称Z是序列X与Y的公共子序列。例如序列"bcba"是序列"abcbdab"与"bdcaba"的公共子序列。例如，给出序列X "hahafdreghsbacdba"和序列"acdbegshbdrabsa"，如何求取这两个序列的最长公共子序列？这道题具有典型的最优子结构特性，即它的最优解一定包含子问题的最优解，这么看使用动态规划来解决是比较...