1.给定两个字符串A和B，同时给定两串的长度n和m。
测试样例："1AB2345CD",9,"12345EF",7 返回：4
public class LongestSubstring { //最长公共子串要求是连续的 public int findLongest(String A, int n, String B, int m) { int max = 0; int[][] dp = new int[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (A.charAt(i) == B.charAt(j)) { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j - 1] + 1; } max = dp[i][j] > max ? dp[i][j] : max; } } return max; } }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0-n之间的数，少了其中一个，怎么找到少的那个
可以用异或
==============================================================================================================
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。 给定字符串A以及它的长度n，请返回最长回文子串的长度。 测试样例： "abc1234321ab",12 返回：7
public class Palindrome { public int getLongestPalindrome(String A, int n) { // write code here int[][] dp = new int[n][n]; int max = 1; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } char[] a = A.toCharArray(); for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (len == 2 && a[i] == a[j]) { dp[i][j] = len; max = 2; continue; } if (a[i] == a[j] && dp[i + 1][j - 1] != 0) { dp[i][j] = len; max = len; } } } return max; } }
动态规划 1.dp[i][j]表示，若i到j已经是回文串了，那么dp[i][j]是回文串的长度，否则为0； 2.初始时dp[i][i]=1，i=0,2,3...n-1； 3.递归公式，len>2时，当dp[i+1][j-1]!=0,且a[i]==a[j]时，dp[i][j] = j-i+1+dp[i+1][j-1], 否则dp[i][j]=0，i<j。这是一个从已知回文串往两边展开的过程。
当len=2时，特殊处理一下，因为当len=2时，dp[i+1][j-1]会访问到dp矩阵的左下方，我们没对那个位置做初始化处理，因此不能直接用递推公式
--------------------------------------------------------------------------------------------------------------------------------------------------------------
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，
给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。
测试样例：
[2,1,4,3,1,5,6],7
时间复杂度为O（N2）的方法如下
public class ZuiChangDiZengZiXulie { public static void main(String[] args) { int[] arr = {2,1,5,3,6,4,8,9,7}; int[] dp = getdp1(arr); int[] lis = generateLIS(arr,dp); for (int i = 0; i < lis.length; i++) { System.out.println(lis[i]); } } public static int[] generateLIS(int[] arr,int[] dp){ int len = arr.length; int max = Integer.MIN_VALUE; int pos = 0; for (int i = 0; i < len; i++) { if(dp[i]>max){ max = dp[i]; pos = i; } } int[] tmp = new int[max]; tmp[max-1] = arr[pos]; max--; for (int i = pos-1; i >=0 ; i--) { if(dp[i] == max){ tmp[max-1] = arr[i]; max--; } } return tmp; } /* 获取最长递增子序列长度 */ public static int[] getdp1(int[] arr){ int[] dp = new int[arr.length]; for (int i = 0; i < arr.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if(arr[i]>arr[j]){ dp[i] = Math.max(dp[i],dp[j]+1); } } } return dp; } }时间复杂度为O（NlogN）的方法如下
public class AscentSequence { public static void main(String[] args) { int[] test = {2, 1, 4, 3, 1, 5, 6}; AscentSequence as = new AscentSequence(); System.out.println(as.findLongest(test)); } public int findLongest(int[] arr) { int length = arr.length; int cur = 0; int[] tmp = new int[length]; tmp[0] = arr[0]; for (int i = 1; i < length; i++) { if (arr[i] > tmp[cur]) { tmp[++cur] = arr[i]; } else { int pos = findpos(tmp, arr[i], 0, cur); tmp[pos] = arr[i]; } } return cur + 1; } //寻找num在数组中的位置 private int findpos(int[] tmp, int num, int start, int end) { while (start < end) { int mid = start + (end - start) / 2; if (tmp[mid] == num) { return mid; } if (tmp[mid] < num) { start = mid + 1; } else { end = mid; } } return start; } }
/*下面一步一步试着找出它。
我们定义一个序列B，然后令i = 0到8逐个考察这个序列。
此外，我们用一个变量end来记录B中最后一个数的下标。
首先，令B[0] = A[0] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2，这时end=0。
然后，把A[2]有序地放到B里，令B[0] = 1，就是说长度为1的LIS的最小末尾是1，B[0]=2已经被淘汰了，这时end =1。
接着，A[2] = 5，A[2]>B[0]，所以令B[1]=A[2]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[0..1] = 1, 5， end＝1。
再来，A[3] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，
长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[0..1] = 1, 3， end = 2。
继续，A[4] = 6，比B中最大的数3还要大 ，于是很容易可以推知B[2] = 6, 这时B[0..2] = 1, 3, 6，end = 2。
A[5] = 4，它在3和6之间，于是我们就要把6替换掉，得到B[2] = 4，B[0..2] = 1, 3, 4，end继续等于2。
A[6] = 8，它很大，比4大。于是继续往B中追加，B[3] = 8， end变成3了。
A[7] = 9，得到B[4] = 9，此时B是1,3,4,8,9，end是4。
最后一个, A[8] = 7，它在4和8之间，所以我们知道，最新的B[3] =7，B[0..4] = 1, 3, 4, 7, 9，end = 4。
于是我们知道了LIS的长度为end+1 = 5。
注意： 这个1,3,4,7,9不是LIS字符串，比如本题例的LIS应该是1,3,4,8,9，7代表的意思是存储4位长度LIS的最小末尾是7，
所以我们的B数组，是存储对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。
虽然最后一个A[8] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字8和9，
那么就可以把8更新到B[4], 9更新到B[5]，得出LIS的长度为6。
然后应该发现一件事情了：在B中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用 二分查找 ，
将每一个数字的插入时间优化到 O(logN)，于是算法的时间复杂度就降低到了O(NlogN)。*/
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class MaxNumber { public static void main(String[] args) { int A[]=new int[]{2,1,-4,3,-1,5,6}; System.out.println(biggest(A,7)); } public static int biggest(int[] A,int length){ int MaxSum=0; int CurSum=0; for(int i=0;i<length;i++){ CurSum+=A[i]; if(CurSum>MaxSum){ MaxSum=CurSum; } if(CurSum<0) CurSum=0; } return MaxSum; } }
换钱的方法数
public class HuanQianDeFangFaShu { public static void main(String[] args) { int[] arr = {5,10,25,1}; System.out.println(coin3(arr,50)); } /* 普通解法 */ public int coins1(int[] arr,int aim){ if(arr == null || arr.length == 0 || aim<0){ return 0; } return process1(arr,0,aim); } private int process1(int[] arr,int index,int aim){ int res = 0; if(index == arr.length){ res = aim==0?1:0; }else { for (int i = 0; arr[index]*i <= aim ; i++) { res += process1(arr,index+1,aim-arr[index]*i); } } return res; } /* 动态规划解法 */ public static int coin3(int[] arr,int aim){ if(arr == null || arr.length == 0 || aim<0){ return 0; } int[][] dp = new int[arr.length][aim+1]; /** * dp[][0]组成钱数为0的方法数，很明显都是1种，也就是 * 不使用任何货币 */ for (int i = 0; i < arr.length; i++) { dp[i][0] = 1; } /** * dp[0][],只使用第一种货币的话，第一种货币的整数倍是1 * 其他的为0 */ for (int i = 1; arr[0]*i <=aim ; i++) { dp[0][arr[0]*i] = 1; } int num = 0; for (int i = 1; i < arr.length ; i++) { for (int j = 1; j <=aim ; j++) { num = 0; /** * 完全不用arr[i]货币，方法数为arr[i-1][j] * 用一张arr[i],剩下的由arr[0...i-1]组成 *方法数为dp[i-1][j-n*arr[i]] */ for (int k = 0; k*arr[i] <= j ; k++) { num += dp[i-1][j-arr[i]*k]; } dp[i][j] = num; } } return dp[arr.length-1][aim]; } }
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1 'B' -> 2 ... 'Z' -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12" 输出: 2 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2:
输入: "226" 输出: 3 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。1.递归暴力解法
public static int process(char[] chs,int i){ //递归终止条件 if(i == chs.length){ return 1; } //不可能以0开头 if(chs[i] == '0'){ return 0; } int res = process(chs, i+1); if(i+1<chs.length&&(chs[i]-'0')*10+chs[i+1]-'0'<27){ res+=process(chs, i+2); } return res; }2.动态规划解法
动态规划关键在于每个阶段状态的把握。
举个例子，比如12224，我们首先对第一位，只能1这种解码方法。
对第二位2，可以1-2（独立），也可以12（合并），两种解码方法。
对第三位2，可以1-2-2（独立），也可以12-2（独立），也可以1-22（合并），三种解码方法。
在这一步我们发现其实到当前位为止的解码方法个数，就是上一步的解码方法个数（在后面直接添加独立的一位）+上一步独立的个数（当然这里要判断能不能合并在一起）。
所以我们只需要记住上一步的解码方法个数和上一步的独立的个数，就可以分不同阶段去处理。
再接下来对第四位2，可以1-2-2-2，也可以12-2-2，也可以1-22-2，这三个都是直接在后面添加独立的一位，也可以1-2-22，也可以12-22，这两个就是把先前独立的一位给合并了，所以当前总的解码个数是3+2=5，当前独立的个数就是3，也是上一步的总解码个数。
过程如下：
1222 独立可合并下一位的个数1123 总的解码方式的个数1235 当前例子11-2
12
1-2-2
12-2
1-22
1-2-2-2
12-2
1-22-2
1-2-22
12-22
规律十分清晰，但我们还有一个情况没有考虑到，就是可能会出现数字0。
比如110，第二个1这一步，当前总的解码方式有1-1和11，两种，独立可合并下一位的个数有一种。
然后到了0这一步，只能合并了，于是总的解码方式变成上一步独立可合并下一位的个数1，解码方式是1-10，当前这一位的独立可合并个数清空为0。
那还有不能合并的呢，比如130，3这一步，仍然是1-3和13，总的有2种，独立的有1种。
到0这一步，不能合并，于是总的解码方式变成0，完全不能解码，返回0。
public static int numDecodings(String s) { if(s == null || s.length()==0 || s.charAt(0)=='0'){ return 0; } //merge 当前可独立合并下一位的个数，既直接把数字加到前面的末尾时。 //total 总的解码个数 int merge = 1,total = 1,sum1,tmp; for (int i = 1; i <s.length() ; i++) { //和前一位合并的值 sum1 = ((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')); //如果数值符合条件，那么可以合并 if(sum1>=1&&sum1<=26){ if(s.charAt(i)!='0'){ tmp = total; //总的解码个数有联股份组成1.直接把数字加到末尾的，就是total。第二与前面的末尾合并。就是merge total+= merge; //merge应该变成当前的total merge = tmp; }else { //当亲位为0，只能与前面的合并 total = merge; merge = 0; } }else { //计算出不能合并 if(s.charAt(i)!='0'){ //当前位置不是0的话，可以直接把数字加到末尾 merge = total; }else { //当前位置为0，既不能加到末尾，又不能合并 return 0; } } } return total; }【题目】给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
【举例】
arr=[5,10,25,1]，aim=0。组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。
arr=[5,10,25,1]，aim=15。组成15元的方法有6种，分别为3张5元，1张10元+1张5元，1张10元+5张1元，10张1元+1张5元，2张5元+5张1元，15张1元。所以返回6。
arr=[3,5]，aim=2。任何方法都无法组成2元。所以返回0。
public static int coinChange(int[] coins, int amount) { int max = amount + 1; int[] dp = new int[amount + 1]; for (int i = 0; i < dp.length ; i++) { dp[i] = max; } dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { //其实和跳台阶思路差不多，可以跳上给定的任一级 //因此这里就是选这次到期用哪种钱可以使得当前值最小 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; }空间压缩
public int minimumTotal(List<List<Integer>> triangle) { if(triangle == null || triangle.size() == 0){ return 0; } int len = triangle.size(); int[] dp = new int[len+1]; int tmp1; for (int i = len-1; i >= 0 ; i--) { int tmp2 = dp[i+1]; for (int j = i; j >= 0 ; j--) { tmp1 = dp[j]; dp[j] = Math.min(tmp2,dp[j])+triangle.get(i).get(j); tmp2 = tmp1; } } return dp[0]; }给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
如果申请一个二维空间的dp[][],那么状态转移方程为dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int row = grid.length; int col = grid[0].length; int[][] dp = new int[row][col]; dp[0][0] = grid[0][0]; for (int i = 1; i < row; i++) { dp[i][0] = grid[i][0] + dp[i - 1][0]; } for (int i = 1; i < col; i++) { dp[0][i] = grid[0][i] + dp[0][i - 1]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[row - 1][col - 1]; } //空间压缩 public int minPathSum1(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int row = grid.length; int col = grid[0].length; int[] dp = new int[col]; //初始化第一行 dp[0] = grid[0][0]; for (int i = 1; i < col; i++) { dp[i] = dp[i - 1] + grid[0][i]; } for (int i = 1; i < row; i++) { dp[0] = grid[i][0] + dp[0]; for (int j = 1; j < col; j++) { dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]); } } return dp[col - 1]; }
