广义上而言，A（A-Star)算法就是一种动态规划算法，只不过A算法在每步迭代计算时作出了更为严格的限制。关于动态规划，可以参考我的另一篇博客：《动态规划及其在Apollo项目Planning模块的应用.

最近在复习算法知识写下这篇文章帮助自己理解记忆01 背包问题01背包问题的目标是在固定的容量限制内，达到最大的物品价值01对含义:无法分割物品01背包问题通常有暴力回溯法和动态规划两种方式来解决Brute Force回溯法检查所有组合 时间复杂度为指数级很容易时间就爆表，这里就不看了动态规划动态规划的核心在于寻找子问...

Given a string, find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any ith character in the two subsequences shouldn’t have the same index in the original string.

最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。而且，这个算法稍加改造就可以用于解决其他问题，所以说 LCS 算法是值得掌握的。

后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态 + 选择，也没啥特别之处嘛。

题目： {代码...} 示例： {代码...} 题目解析： {代码...} 代码： {代码...}

(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

利用了动态规划求解01背包问题的方法 {代码...}

很多人觉得动态规划很难，甚至认为面试出动态规划题目是在为难候选人，这可能产生一个错误潜意识：认为动态规划不需要掌握。其实动态规划非常有必要掌握：非常锻炼思维。动态规划是非常锻炼脑力的题目，虽然有套路，但每道题解法思路差异很大，作为思维练习非常合适。非常实用。动态规划听起来很高级，但实际上思路和解...

70. 爬楼梯难度：简单假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定n是一个正整数。我的题解：

题目描述（困难难度） 字符串匹配，? 匹配单个任意字符，* 匹配任意长度字符串，包括空串。和第 10 题有些类似。 解法一 动态规划 直接按照之前第 10 题，修改一下就可以了。 同样是用 dp[i][j] 表示所有的情况，然后一层一层的根据递推关系求出来。 {代码...} 时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O...

动态规划，英文：Dynamic Programming，简称DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使价值总和最大（每一种物品只能放一次）

答：在AVL树中，节点的最少个数可以通过递归计算得到。AVL树是一种自平衡的二叉搜索树，它的高度可以表示为h，其中h是树的高度。AVL树的高度与节点数之间存在如下关系：

工作了两年，之前一直沉浸在业务当中，感觉算法的用处不太大，在这两年的时间里跟算法相关的也就写过一个很基础的递归函数。刷过几道leetcode，每次做题花费的时间都很长，而且做了感觉对实际上的工作没啥帮助。事实证明，我还是太肤浅

动态规划算法一直是面试手撕算法中比较有挑战的一种类型。很多的分配问题或者调度问题实际上都可能用动态规划进行解决。（当然，如果问题的规模较大，有时候会抽象模型使用动归来解决，有时候则可以通过不断迭代的概率算法解决查找次优解）

典型的动态规划题。维护一个二维数组dungeon，dungeon[i][j]表示从第i行第j出发到终点所需要的最低血量（包含当前位置的消耗），最低血量不大于1。