题目：给定两个字符串str1和str2，再给定3个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。例：str1=”abc”,str2=”adc”,ic=5,dc=3,rc=2.将’b’替换成’d’代价是最小的，返回代价2。str1=”abc”,s ...

题目：给定两个字符串，返回两个字符串的最长公共子串。例：str1=”1AB2345CD”，str3=”12345EF”，返回”2345”。str1=”abcde”，str2=”bebcd“。最长公共子串为”bcd”。要求：若str1和str2的长度分别为M和N，要求时间复杂度为O(M*N)，额外的空 ...

注意try块的使用：由于finally语句较臃肿，Java7允许try关键字后面跟一对圆括号，括号中声明或初始化那些必须在程序结束时显式关闭的资源。这些资源必须实现AutoCloseable接口或其子接口Closeable接口。AutoCloseable接口里的close()方法声明抛出了Excep ...

例：str1 = “1A2C3D4B56“;str2 = “B1D23CA45B6A”则最长公共子序列为”12C4B6”。 实现：动态规划（注意公共子序列中的每个字符可能不连续）步骤一：str1的长度为M，str2的长度为N，生成大小为M*N的矩阵dp，dp[i][j]表示使用str[0,…i]与s ...

Hanio汉诺塔问题：将所有的盘子从塔A移到塔C，且每次移动一个盘子，上面的盘子比下面的盘子大。 实现：利用递归。无论有多少个盘子，都将其看做只有两个盘子。假设有 N 个盘子在塔座A上，将其看做两个盘子，其中第(N-1)1个盘子看成是一个盘子，最下面第N个盘子看成是一个盘子，那么解决办法为：①、先将 ...

题目：给定数组arr=[2,1,5,3,6,4,8,9,7]，返回最长递增子序列，即[1,3,4,8,9]。要求：若arr长度为N，时间复杂度为O(NlogN)。 实现方法一：时间复杂度为O(N^2)步骤一：生成长度为N的数组dp，dp[i]表示以arr[i]这个数结尾的情况下，arr[0,…i]中 ...

题目：给定数组arr，所有值都为正且不重复。每个值代表一种货币，每种货币可以使用任意张，给定一个整数aim，求换钱有多少种方法。arr = {5, 10, 25, 1}，aim=15，组成15的方法有6种。 分析：暴力递归，记忆搜索，动态规划。实现：动态规划建立 M*（aim+1)的二维数组dp，d ...

题目：给定数组arr,arr中的值可以重复，其中每个值代表一张货币，因此不能重复使用。给定一个数aim，求组成aim的最少货币数。例：arr=[5,2,3]，aim=0，不用任何货币就能组成0元，返回0。arr=[5,2,3]，aim=20,由于不能重复使用，5+2+3<20，不能组成，返回- ...

题目：给定一个数组arr，arr中的值不重复，每个值代表一种货币，但每种可以重复使用。给定一个整数aim，求组成aim值的最少货币数。 实现：如果arr的长度为N，则生成行数为N*（aim+1）的动态规划矩阵dp。时间复杂度和额外的空间复杂度都为O（N*aim）。dp[i][j]的含义是，在任意使 ...

题目：给定一个矩阵m,从左上角开始，每次只能向下或向右走一步，最后达到右下角的位置。路径上所有的数字累加起来就是路径和，返回所有的路径和中最小的路径和。1 3 5 98 1 3 45 0 6 18 8 4 0 分析： 先生成与m大小一样的矩阵dp，dp[i][j]表示从左上角（即(0,0)位置）走 ...