以前ACM时期，一开始学习动态规划时，并不懂这个东西到底是个什么概念。搜索题解，大部分往往也是甩个题目，然后直接列出状态转移方程，紧接着直接来个AC代码，让人云里雾里。尽管做过一些题目，但是往往遇到新的题目便抓瞎了。只会一些做过的题，例如导弹拦截，各种背包。今天借助算法课的作业，仔细的将动态规划剖析一...

零 标题：算法（leetcode，附思维导图 + 全部解法）300题之（剑指 Offer II 091）粉刷房子一 题目描述二 解法总览（思维导图）三 全部解法1 方案11)代码： {代码...} 2 方案21)代码： {代码...} 四 资源分享 & 更多1 历史文章 - 总览文章名称解法阅读量1. 两数之和（Two Sum）共 3 种2.7 k+2. 两数相加 （Add Two Number...

动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给...

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

明确了问题，其实就已经把问题解决了⼀半。即然耗时的原因是重复计算， 那么我们可以造⼀个「备忘录」，每次算出某个⼦问题的答案后别急着返 回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查 ⼀查，如果发现之前已经解决过这个问题了，直接把答案拿出来⽤，不要再 耗时去计算了。 ⼀般使⽤⼀个数组...

假设师傅每天工作 8 个小时，给定一天 n 个订单，每个订单其占用时间长为 $T_i$，挣取价值为 $V_i$，现请您为师傅安排订单，并保证师傅挣取价值最大。

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单...

广义上而言，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)

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

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

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