algorithm-go's People
algorithm-go's Issues
1
第一个标题
- a
- b
第二个
动态规划
1.动态规划介绍
动态规划,英文:Dynamic Programming,简称DP,动态规划的思路一般是把一个复杂问题转化成一个个子问题, 然后分阶段逐步递推, 从一个简单的初始状态一步一步递推, 最终得到一个复杂问题的最优解, 动态规划也有分治的**.
1.1解决的问题
动态规划问题的形式大部分都是求最值, 或者最优解, 比如有求最长递增子序列, 最长公共子序列等等.
- 子序列问题
- 背包类型问题
- 贪心类型问题
1.2使用限制
- 重叠子问题
一个问题可以拆分成很多个子问题, 并且在求解过程中存在同样的子问题重复计算 - 最优子结构
问题的最优解包含子问题的最优解, 也就是说可以根据一个子问题的最优解, 推导出这个问题的最优解, 对应到动态规划问题之上, 也就是后面阶段的状态可以通过前面状态推导出来, 并且子问题之间互相独立. - 无后效性
主要有两个含义. 第一, 在推导后面问题或者阶段状态的时候,我们只关心前面的状态值,不关心这个状态值是怎么一步步推导出来的. 第二, 某阶段状态值一旦确定,就不受之后阶段的决策影响.
1.3解题步骤
一般动态规划解决的都是最值问题, 而求解最值的核心方法是穷举, 但是因为重叠子问题的特性,直接穷举效率很低, 所以通过备忘录的形式优化穷举过程, 一般叫: dp table. 又因为最优子结构的特性, 那么可以通过子问题的最值得到问题的最值. 大部分的动态规划问题都会经历下面几个步骤:
- 划分状态, 也就是确定划分子问题及含义
- 确定状态表示
确定dp数组(dp table)值以及下标的含义 - 确定状态转移
父问题如何通过子问题推导出来的,也就是上一阶段状态如何推导出本阶段的状态 - 确定边界
也就是明确问题的初始状态及最终状态, 一般需要确定初始状态, 也就是初始化 dp table 的值, 然后求出最终状态
总结套路就是
# 初始化 dp table
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1,选择2...)
1.4实现方式
- 递归
这种方式是自上向下的,通过dp(n)到dp(n-1) - 递推
这种方式是自下向上的,通过dp(0) 推导出 dp(1), 再由 dp(2) 推导出 dp(3)
2.过程举例
2.1斐波那契数列-重叠子问题
(1) 暴力递归
int f(int N) {
if (N == 1 || N == 2) return 1;
return f(N - 1) + f(N - 2);
}
计算原问题 f(20),就要先计算出子问题 f(19) 和 f(18),然后要计算 f(19),就要先算出子问题 f(18) 和 f(17),以此类推。最后遇到 f(1) 或者 f(2) 的时候,结果已知,就能直接返回结果,递归树不再向下生长了。在这个过程中,会发现有很多子问题被重复计算,这就是动态规划的第一个性质: 重叠子问题 .
(2) 带备忘录的递归
int f(int N) {
// 备忘录全初始化为 0
int[] memo = new int[N + 1];
// 进行带备忘录的递归
return helper(memo, N);
}
int helper(int[] memo, int n) {
// 确定边界
if (n == 0 || n == 1) return n;
// 已经计算过,不用再计算了
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
通过递归树,可以看到备忘录避免了重复计算,这种方式已经和动态规划解法差不多了, 然后这种递归的方式就是我们刚刚说的自上向下的解法: ** 都是从一个规模较大的原问题比如说 f(20),向下逐渐分解规模,直到 f(1) 和 f(2) 这两个 base case,然后逐层返回答案 ** , 自下向上就是反过来, 直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)(边界,初始状态)开始往上推,直到推到想要的答案 f(20)。这就是「递推」的思路,大部分动态规划都是使用递推,而是由循环迭代完成计算.
(4) dp 数组递推解决
上述中的备忘录就叫做 DP table . 通过这个表 自下向上 进行递推, 得到结果
int fib(int N) {
if (N == 0) return 0;
int[] dp = new int[N + 1];
// 初始化状态
dp[0] = 0; dp[1] = 1;
// 进行状态转移
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
2.2 零钱兑换-状态转移方程
解决步骤
- 判断最优子结构
比如想求 amount = 11 时的最少硬币数,如果知道凑出 amount = 10 的最少硬币数(子问题),那么只需要把子问题的答案加一(再选一枚面值为 1 的硬币)就是原问题的答案。因为硬币的数量是没有限制的,所以子问题之间没有相互制,是互相独立的。 - 确定状态
原问题和子问题中会变化的变量。由于硬币数量无限,硬币的面额也是题目给定的,只有目标金额可以分解成子问题,所以唯一的「状态」就是目标金额 amount - 确定状态表示
首先讨论自顶向下的解法,会有一个递归的 dp 函数,函数的参数就是状态转移中会变化的量,也就是上面说到的「状态」;函数的返回值就是题目要求我们计算的值。就本题来说,状态只有一个,即「目标金额」,题目要求我们计算凑出目标金额所需的最少硬币数量。 - 初始化状态
当目标金额 amount 为 0 时算法返回 0
所以我们可以这样定义 dp 函数:dp(n) 表示,输入一个目标金额 n,返回凑出目标金额 n 所需的最少硬币数量。
递归解法
// 定义:要凑出金额 amount/n,至少要 dp(coins, amount) 个硬币
int dp(int[] coins, int amount) {
// 边界条件
if (amount == 0) return 0;
int res = Integer.MAX_VALUE;
if (amount < 0) return Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解则跳过
if (subProblem == Integer.MAX_VALUE) continue;
// 在子问题中选择最优解, 选择硬币最少的解,然后加上当前需要的一枚硬币
res = Math.min(res, subProblem + 1);
}
return res;
}
递推解法
自底向上使用 dp table 来消除重叠子问题,关于「状态」「选择」和 base case 与之前没有区别,dp 数组的定义和刚才 dp 函数类似,也是把「状态」,也就是目标金额作为变量。不过 dp 函数体现在函数参数,而 dp 数组体现在数组索引:
dp 数组的定义:当目标金额为 i 时,至少需要 dp[i] 枚硬币凑出。
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 数组大小为 amount + 1,初始值也为 amount + 1, 表示无解
Arrays.fill(dp, amount + 1);
// base case
dp[0] = 0;
// 外层 for 循环在遍历所有状态的所有取值
for (int i = 0; i < dp.length; i++) {
// 内层 for 循环在求所有选择的最小值
for (int coin : coins) {
// 子问题无解,跳过
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
3.例题
最长递增子序列
首先定义 dp table: dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
根据这个定义, 就可以确定初始状态: dp[i] 全部初始化为 1, 因为以 nums[i] 结尾的递增子序列至少包括它自己.
演示:
根据以上,那么 dp table 中最大的值就是这道题的结果
如果已经知道了 dp[0...4] 的值, 那么如何根据已知结果推导出 dp[5] 的值呢?
按照对 dp 数组的定义, 现在想求 dp[5] 的值,也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3,既然是递增子序列,我们只要找到前面那些结尾比 3 小的子序列,然后把 3 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一, 可能形成很多种新的子序列,但是只选择最长的那一个,把最长子序列的长度作为 dp[5] 的值即可
int lengthOfLIS(int[] nums) {
// 定义:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
int[] dp = new int[nums.length];
// 初始化dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.