1.求一个整数序列的最长递增子序列。
2.编辑距离算法。即从一个字符串转换成另一个字符串的最少操作次数。允许添加,删除或是替换字母。
3.两个整数数组,从每个数组中有序取m个数,两两相乘后的和最大。求最大和。
4.求两个字符串的最长公共子串。
java 代码
2.编辑距离算法。即从一个字符串转换成另一个字符串的最少操作次数。允许添加,删除或是替换字母。
- public int getDistance(String s1, String s2) {
- int[][] array = new int[s1.length() + 1][s2.length() + 1];
- for (int i = 0; i <= s1.length(); i++) {
- array[i][0] = i;
- }
- for (int j = 0; j <= s2.length(); j++) {
- array[0][j] = j;
- }
- for (int i = 1; i <= s1.length(); i++) {
- for (int j = 1; j <= s2.length(); j++) {
- array[i][j] = Integer.MAX_VALUE;
- array[i][j] = Math.min(array[i][j], array[i - 1][j] + 1);
- array[i][j] = Math.min(array[i][j], array[i][j - 1] + 1);
- int c = s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1;
- array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + c);
- }
- }
- return array[s1.length()][s2.length()];
- }
java 代码
3.两个整数数组,从每个数组中有序取m个数,两两相乘后的和最大。求最大和。
- public int getMaxMulti(int[] a, int[] b, int N) {
- int[] a1 = new int[a.length + 1];
- int[] a2 = new int[b.length + 1];
- for (int i = 0; i < a.length; i++) {
- a1[i + 1] = a[i];
- }
- for (int i = 0; i < b.length; i++) {
- a2[i + 1] = b[i];
- }
- int[][][] m = new int[N + 1][a1.length][a2.length];
- for (int k = 1; k <= N; k++) {
- for (int i = k; i < a1.length; i++) {
- for (int j = k; j < a2.length; j++) {
- int max = Integer.MIN_VALUE;
- if (i - 1 >= k) {
- max = Math.max(max, m[k][i - 1][j]);
- }
- if (j - 1 >= k) {
- max = Math.max(max, m[k][i][j - 1]);
- }
- max = Math.max(max, m[k - 1][i - 1][j - 1] + a1[i] * a2[j]);
- m[k][i][j] = max;
- }
- }
- }
-
- return m[N][a.length][b.length];
- }
java 代码
- //最长公共字串
- public class LongestCommonSequence {
-
-
-
-
- public static void main(String[] args) {
- System.out
- .println(new LongestCommonSequence().getLCS("pailbyujcdfefdghijk", "abcaduefsgdhdijdfk"));
-
- }
-
- public String getLCS(String s1, String s2) {
- int[][] lens = new int[s1.length() + 1][s2.length() + 1];
-
- int[][] directions = new int[s1.length() + 1][s2.length() + 1];
- for (int i = 1; i <= s1.length(); i++) {
- for (int j = 1; j <= s2.length(); j++) {
- if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
- lens[i][j] = lens[i - 1][j - 1] + 1;
- directions[i][j] = 0;
- } else if (lens[i][j - 1] >= lens[i - 1][j]) {
- lens[i][j] = lens[i][j - 1];
- directions[i][j] = 1;
- } else {
- lens[i][j] = lens[i - 1][j];
- directions[i][j] = -1;
- }
- }
- }
-
- return getCommon(s1, directions, s1.length(), s2.length());
- }
-
- private String getCommon(String s1, int[][] directions, int len1, int len2) {
- if (len1 == 0 || len2 == 0) {
- return "";
- }
- if (directions[len1][len2] == 0) {
- return getCommon(s1, directions, len1 - 1, len2 - 1) + s1.charAt(len1 - 1);
- } else if (directions[len1][len2] == 1) {
- return getCommon(s1, directions, len1, len2 - 1);
- } else {
- return getCommon(s1, directions, len1 - 1, len2);
- }
- }
- }
分享到:
相关推荐
动态规划 动态规划 动态规划 动态规划 动态规划 动态规划
代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的...
动态规划是信息学竞赛中的常见算法,本文的主要内容就是分析 它的特点。 文章的第一部分首先探究了动态规划的本质,因为动态规划的特 点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个 角度分析了动态...
在计算机算法设计方法中,动态规划技术是比较基本,但又比较抽象,难于理解的一种。它建立在最优原则的基础上,动态规划 ( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,...
(1) 动态规划算法设计思想。 (2) 金罐游戏问题的动态规划解法。 算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和...
动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”,指的是在问题的多阶段决策中,按某一顺序,根据每一步所选决策的不同,将随即引起状态的转移,最终在变化的状态中产生一个决策序列。动态规划就是...
矩阵相乘问题的动态规划,动态规划是解决多阶段决策过程最优化问题的一种方法,其思想是将求解的问题一层一层地分解成一级一级的子问题,子问题的求解由繁到简逐步缩小,直到可以直接解出子问题为止。下面用动态规划...
会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验性质】 验证性实验(学时数:2H) 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略...
学习动态规划必备~ 动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~
动态规划是求解最优化问题的一种方法;动态规划虽然空间复杂度一般较大,但时间效率可观。但是,动态规划在求解中也会存在一些不必要、或者重复求解的子问题,这时就需要进行进一步优化。 在NOI及省选赛场上,一般...
几道动态规划的经典算法 非常经典 值得分享
java 最短路径 问题 动态规划java 最短路径 问题 动态规划
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
这是一份简单的动态规划实验报告,独立完成的,参考了一些资料
详细阐述动态规划的应用范围及方法 动态规划经典教程 引言:本人在做过一些题目后对DP有些感想,就写了这个总结: 第一节 动态规划基本概念 一,动态规划三要素:阶段,状态,决策。 他们的概念到处都是,我就不多说...
动态规划是解决多阶段决策问题最优化的一种数学方法,大约产生于50年代,1951年美国数学家数学家贝尔曼(R.Bellman)等人根据多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段问题,然后逐个加以...
动态规划混合动力汽车模式切换程序,附带工况。
经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。...代码包含遗传算法和动态规划来求解这个问题,里面有完整源代码,并且有详细注释,还有两者的比较分析。
12个ACM动态规划经典题 习题+分析+程序 (转载)