public int maxProfit(int[] prices) { int n = prices.length; if (n==0) return 0; // 最多两次买卖 两次 买卖 一共有五个阶段 int[][] f = new int[n+1][6]; // 1 持币观望 2 买入 3卖出 持币观望 4 第二次买入 5 第二次卖出 持币观望 f[0][1] = 0; //前0天 一阶段 最大获利 为 0 f[0][2] = Integer.MIN_VALUE; f[0][3] = Integer.MIN_VALUE; f[0][4] = Integer.MIN_VALUE; f[0][5] = Integer.MIN_VALUE; // 1 3 5 for (int i = 1; i <=n ; i++) { for (int j = 1; j <=5 ; j+=2) { f[i][j] =f[i-1][j]; if (j>1&&i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]); } } for (int j = 2; j <=5 ; j+=2) { f[i][j] = f[i-1][j-1]; if (i>1&&f[i-1][j]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]); } if (j>2&&i>1&&f[i-1][j-2]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j-2]+prices[i-1]-prices[i-2]); } } } return Math.max(f[n][1],Math.max(f[n][3],f[n][5])); }

 

 

 

 

 

 

public int maxProfit(int k, int[] prices) { // write your code here int n = prices.length; if (n==0 ) return 0; if (k>n) { int res =0; for (int i = 0; i <n-1 ; i++) { res+= Math.max(0,prices[i+1]-prices[i]); } return res; } int f[][] = new int[n+1][2*k+2]; //描述右2k+1个阶段 f[0][1] =0; for (int i = 2; i <2*k+2 ; i++) { f[0][i] = Integer.MIN_VALUE; } for (int i = 1; i <=n ; i++) { for (int j = 1; j <=2*k+1 ; j+=2) { f[i][j] =f[i-1][j]; if (j>1&&i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]); } } for (int j = 2; j <=2*k+1 ; j+=2) { f[i][j] = f[i-1][j-1]; if (i>1&&f[i-1][j]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]); } if (i>1&&j>2&&f[i-1][j-2]!=Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i-1][j-2]+prices[i-1]-prices[i-2]); } } } int max =0; for (int i = 0; i <=2*k+1 ; i++) { max =Math.max(max,f[n][i]); } return max; }

 

 

 

 

 

 

public int longestIncreasingSubsequence(int[] nums) { // write your code here int n = nums.length; if (n==0) return 0; int[] f = new int[n]; // f[i] 表示 以 nums[i] 结尾的最长上升子序列的长度 int res =0; for (int i = 0; i <n ; i++) { f[i] =1; for (int j = 0 ; j <i ; j++) { if (nums[i]>nums[j]&&f[j]+1>f[i]){ f[i] = f[j]+1; } res = Math.max(res,f[i]); } } return res; }

 

 

 

n2算法 

public int maxEnvelopes(int[][] envelopes) { // write your code here Arrays.sort(envelopes, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if (o1[0]==o2[0]){ return o1[1]-o2[1]; }else { return o1[0]-o2[0]; } } }); //先将信封 排序 int n = envelopes.length; if (n<=1) return n; int[] f= new int[n]; //f[i] 表示以 e[i] 为 最外层的最多嵌套层数 f[0] = 1; for (int i = 0; i <n ; i++) { f[i]=1; for (int j = 0; j <i ; j++) { if (envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1]){ f[i]=Math.max(f[i],f[j]+1); } } } int res = 0 ; for (int i = 0; i <n ; i++) { res = Math.max(res,f[i]); } return res; }

 

 

 

public int numSquares(int n) { // write your code here int f[] = new int[n+1]; // f[i] 表示最大的完全平方数是多少 Arrays.fill(f,Integer.MAX_VALUE); f[0] = 0; f[1] = 1; for (int i = 0; i <n+1 ; i++) { int t=(int)Math.pow(i,0.5); if (t*t==i){ f[i]= 1; }else { for (int j = i-1; j >0 ; j--) { f[i] =Math.min( f[j] + f[i-j],f[i]); } } } System.out.println( Arrays.toString(f)); return f[n]; }

 

public int numSquares(int n) { // write your code here int f[] = new int[n+1]; // f[i] 表示最大的完全平方数是多少 Arrays.fill(f,Integer.MAX_VALUE); f[0] = 0; for (int i = 0; i <n+1 ; i++) { for (int j = 1; j*j <=i ; j++) { if (f[i-j*j]+1<f[i]){ f[i] =f[i-j*j]+1; } } } return f[n]; }

 

public int minCut(String ss) { // write your code here char s[] = ss.toCharArray(); int n = ss.length(); if (n==0) return 0; boolean[][] isPalin = new boolean[n][n]; int i,j; for (int t = 0; t <n ; t++) { i=j=t; //奇数 while (i>=0&&j<n&&s[i]==s[j]){ isPalin[i][j] = true; --i; ++j; } //偶数 i=t; j=t+1; while (i>=0&&j<n&&s[i]==s[j]){ isPalin[i][j] =true; i--; j++; } } int[] f =new int[n+1]; f[0] = 0 ; for (int k = 1; k <=n ; k++) { f[k] =Integer.MAX_VALUE; for (int l = 0; l <k ; l++) { if (isPalin[l][k-1]){ f[k] = Math.min(f[k],f[l]+1); } } } return f[n]-1; }

//划分型动态规划

 

 

public int copyBooks(int[] pages, int k) { // write your code here int n = pages.length; if (n==0) return 0; int max =0; for (int i = 0; i <n ; i++) { max=Math.max(pages[i],max); } if (k>n) return max; int[][] f = new int[k+1][n+1]; // k个抄写员最少需要多少时间抄完前i本书 for (int i = 1; i <n+1 ; i++) { f[0][i] =Integer.MAX_VALUE; } for (int i = 1; i <k+1 ; i++) { f[i][0] = 0; for (int j = 1; j <n+1 ; j++) { f[i][j] = Integer.MAX_VALUE; int sum = 0; for (int l = j; l >=0 ; l--) { f[i][j] = Math.min(f[i][j],Math.max(f[i-1][l],sum)); if (l>0){ sum +=pages[l-1]; } } } } return f[k][n]; }

 

 

博弈型动态规划

 

 

 

 

public boolean firstWillWin(int n) { // write your code here if(n==0) return false; if(n<=2) return true; //先手必胜 boolean[] f= new boolean[n+1]; f[0] =false; f[1] = f[2] =true; for(int i = 3; i<=n;i++){ f[i] =!f[i-1]||!f[i-2]; } return f[n]; }

 

背包问题

 

 

 

 

 

 

 

//背包问题要把总承重放入状态

 

public int backPack(int m, int[] A) { // write your code here Arrays.sort(A); int n = A.length; boolean[][] f = new boolean[n+1][m+1]; //背包 问题 就是 第i个物品 选还是不选 质量 // f[i] =Math.max(f[i-1]+A[i-1],f[i-1]) m = m - a[i] 所以应该是个二维问题 f[0][0] =true; for (int i = 1; i <=n ; i++) { for (int j = 0; j <=m ; j++) { f[i][j] = f[i-1][j]; if (j-A[i-1]>=0){ f[i][j]=f[i][j]||f[i-1][j-A[i-1]]; } } } for (int i = m; i >=0 ; i--) { if (f[n][i]==true) return i; } return 0; }

 

 

public static int backPack(int m, int[] A) { // write your code here int n= A.length; if (n==0) return 0; int f[] = new int[m+1]; int pai[] = new int[m+1]; f[0] =1; for (int i = 1; i <=m ; i++) { f[i]=0; for (int j = 0; j <n ; j++) { if (i>=A[j]){ f[i] +=f[i-A[j]]; if (f[i-A[j]]>0){ pai[i] = A[j]; } } } } if (f[m]>0){ int i=m; System.out.println(i+" = "); while (i!=0){ System.out.print(pai[i]+" "); i-=pai[i]; } } return f[m]; }

 

 

 

 

public static int backPack(int m, int[] W,int[] V) { // write your code here int n = W.length; int f[][] = new int[n+1][m+1]; f[0][0] = 0; //价值 为0; for (int i = 1; i <n+1 ; i++) { for (int j = 0; j <m+1 ; j++) {// if (j>W[j-1]&&f[i-1][i-W[j-1]]>0); f[i][j] = Math.max(f[i-1][j],f[i-1][j-W[j-1]]+V[j-1]); } } return f[n][m]; } public static int backPackII(int m, int[] W,int[] V) { int n = W.length; if (n==0) return 0; int[] f = new int[m+1]; f[0] = 0; for (int i = 1; i <=m ; i++) { f[i]=-1; } int res=0; for (int i = 1; i <=n ; i++) { for (int w = m; w >=0 ; w--) { if (w>=W[i-1]&&f[w-W[i-1]]!=-1){ f[w] =Math.max(f[w],f[w-W[i-1]]+V[i-1]); } res =Math.max(res,f[w]); } } return res; }

 

 

public static int backPack( int[] V,int[] W,int m) { //每个物品能使用无限多次 int n = W.length; int[] f = new int[n+1]; int res =0; for (int i = 1; i <=n ; i++) { for (int j = W[i]; j <=m ; j++) { f[j]=Math.max(f[j],f[j-W[i-1]]+V[i-1]); } } return f[m]; }

 

 

 

public int longestPalindromeSubseq(String ss) { // write your code here char[] s = ss.toCharArray(); int n = s.length; if (n==0) return 0; int[][] f = new int[n][n]; for (int i = 0; i <n ; i++) { f[i][i]=1; } for (int i = 0; i <n-1 ; i++) { f[i][i+1] = (s[i]==s[i+1])?2:1; } for (int len = 3; len <=n ; len++) { for (int i = 0; i <=n-len ; i++) { int j = i+len-1; f[i][j] = Math.max(f[i][j-1],f[i+1][j]); if (s[i]==s[j]){ f[i][j] = Math.max(f[i][j],f[i+1][j-1]+2); } } } return f[0][n-1]; }

 记忆化搜索

int[][] f; char[] s; public int longestPalindromeSubseqII(String ss) { // write your code here s = ss.toCharArray(); int n = s.length; if (n==0) return 0; f = new int[n][n]; for (int i = 0; i <n ; i++) { for (int j = i; j <n ; j++) { f[i][j] = -1; } } Compute(0,n-1); return f[0][n-1]; } public void Compute(int i,int j){ if (f[i][j]!=-1) return; if (i==j) { f[i][j]=1; return; } if (i+1==j){ f[i][j] = (s[i]==s[j])?2:1; return; } Compute(i,j-1); Compute(i+1,j); Compute(i+1,j-1); f[i][j] = Math.max(f[i][j-1],f[i+1][j]); if (s[i]==s[j]){ f[i][j] = Math.max(f[i][j],f[i+1][j-1]+2); } }

 

 

q区间型动态规划 

private static boolean f(int[] a) { int n= a.length; if (n==0) return true; int[][] f = new int[n][n]; for (int i = 0; i <n ; i++) { f[i][i] = a[i-1]; for (int len = 2; len <=n ; len++) { for (int i = 0; i <=n-len ; i++) { int j = i+len-1; f[i][j] = Math.max(a[i]-f[i+1][j],a[j]-f[i][j-1]); } } } return f[0][n-1]>=0; }

 

public boolean isScramble(String ss1, String ss2) { // write your code here char[] s1 = ss1.toCharArray(); char[] s2 = ss2.toCharArray(); if (s1.length!=s1.length) return false; int n = s1.length; boolean[][][] f = new boolean[n][n][n+1]; for (int i = 0; i <n ; i++) { for (int j = 0; j <n ; j++) { f[i][j][1]=s1[i]==s2[j]; } } for (int k = 2; k <=n ; k++) { for (int i = 0; i <=n-k ; i++) { for (int j = 0; j <=n-k ; j++) { f[i][j][k] = false; for (int w = 1; w <k ; w++) { if (f[i][j][w]&&f[i+w][j+w][k-w]){ f[i][j][k] =true; break; } if (f[i][j+k-w][w]&&f[i+w][j][k-w]){ f[i][j][k] =true; break; } } } } } return f[0][0][n]; }

public int maxCoins(int[] B) { // write your code here int n = B.length; if (n==0) return 0; int[] A = new int[n+2]; A[0]=A[n+1]=1; for (int i = 1; i <=n ; i++) { A[i] =B[i-1]; } int[][] f = new int[n+2][n+2]; for (int i = 0; i <n+1 ; i++) { f[i][i+1] = 0; } for (int len = 3; len <=n+2 ; len++) { for (int i = 0; i <n+2 ; i++) { int j = i+len-1; if(j>n+1) break; f[i][j] =0; for (int k = i+1; k <j ; k++) { f[i][j] = Math.max(f[i][j],f[i][k]+f[k][j]+A[i]*A[k]*A[j]); } } } return f[0][n+1]; }