Algorithm: dynamic programming
1. Longest Increasing Subsequence (LIS) problem
unsorted array, calculate out the maximum length of subsequence with non-decreasing order.
lis[i] = lis[j] + 1 if arr[i] > arr[j]; lis[i] is the lis with arr[i] as the last element. so to get the maximum for the whole array, we should iterate the array and find out the max(lis[i])
complexity: O(n^2)
better algorithm: O(n logn): http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
2. Longest common subsequence
f[i][j] = f[i-1][j-1]+1 if s1[i-1] == s2[j-1]
max(f[i-1][j], f[i][j-1]) else
3. edit distance
f[i][j] = f[i-1][j-1] if f[i-1] == f[j-1];
min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;
4. coin change
N cents, infinitely supply S = {S1, S2, ... Sm}, how many way to change it?
f[i][j] = f[i-s[j]][j] + f[i][j-1], i: the cents, j: using 0 to j Sj to change it.
5. matrix chain multiplication
for (L = 2; L < n; L++) { // L is the chain length
for (int i = 1; i <= n-L+1; i++) {
j = i+L-1;
m[i][j] = INT_MAX;
for (int k = i; k <= j-1; k++) {
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
m[i][j] = min(m[i][j], q);
}
}
}
return m[1][n-1];
最新文章
- TeamCity : 安装 Server
- js的touch事件的实际引用
- CodeForces 209C Trails and Glades
- 【BZOJ】1513: [POI2006]Tet-Tetris 3D
- img test
- Java 实现组合(Composite)模式
- 使用Protel99 SE 拼板的详细图解（新加队列粘贴方法）
- switch实现一个两数的运算
- python入门基础
- Mysql B+Tree原理
- 创建ajax的步骤
- Vue 错误记录：Cannot read property 'beforeRouteEnter' of undefined
- BZOJ1969 航线规划
- windows 模拟用户会话创建进程
- CentOS 配置Tomcat服务脚本
- Codeforces 946D Timetable（预处理+分组背包）
- 使用Bus.js进行兄弟(非父子)组件通信
- Elasticsearch（9）：使用Logstash-input-jdbc同步数据库中的数
- css贝塞尔曲线模仿饿了么购物车小球动画
- [LeetCode] string整体做hash key，窗口思想复杂度O(n)。附来自LeetCode的4例题(标题有字数限制，写不下所有例题题目 T.T)