1. Determine the dimension of the array. If it is a one-dimensional array, do not complicate the problem.
2. When there is no thought, the penultimate part of finite consideration is set to X;
3. Subsequence problems want to end at every position
4. The minimum value problem does not need to think about logic, as long as the classification uses min, Max
5. The first step in the problem is to determine the dimensions
6. When two-dimensional dynamic programming is clear about the ergodic sequence of I and J, observe the formula and make logical deduction
7. Process = several dimensional variables = what type of judgment is = deduction of a formula = deduction of a (judge to go first x or y, some do not affect can be written arbitrarily, some have influence) = boundary conditions
8. Dynamic planning
Dp - coordinates, ending with I/sequential dp- I/partition type - I, deduce using j to satisfy the condition/interval type f (I, j) from I to j/ double sequence type, two stringsCopy the code9. Dynamic game planning starts from the first step
10. In the backpack problem, the size of the array depends on the total load
Dp currently encountered
1. Shortest edit distance, first I first j, f [n+1] [m+1],
Position i-1 == position j-1 f [I] [j] = position f [i-1] [J-1]
Math. Min (f [i-1,j],f [i-1,j-1],f [i-1,j-1])+1
2. The longest subroutine string
F [I +1] [j-1] ==true&& s.charat (I)== s.charat (j)
sample
###1 How many ways can I go from the top left corner to the bottom right corner?
public static int findMIn(int m,int n){ int[][] f = new int[m+1][n+1]; f[0][0]=0; f[0][1]=1; f[1][0]=1; for(int i = 1; i<m+1; i++){ for(int j =1; j<i; j++){ f[i][j]= f[i-1][j]+f[i][j-1]; } } return f[m][n]; }Copy the codeN ^2 = n^2 = n^2 = n^2
public static boolean findhow(int[] bu){ int len =bu.length; boolean[] f = new boolean[len]; f[0]=true; for(int i =1; i<len; i++){ for(int j=0; j<i; j++){ if(f[j]==true && i-j<bu[j]){ f[i] = true; } } } return f[len-1];Copy the code}
O (n^2*k)
public static int eggs(int lou,int dan){ int[][] f = new int[lou+1][dan+1]; for(int a =1; a<=lou; a++){ f[a][1] = a; } for(int b =1; b<=dan; b++){ f[1][b] = 1; } for(int i = 2; i<=lou; i++){ for(int j =2; j<=dan; j++){ f[i][j] =Integer.MAX_VALUE; for(int k=1; k<i; K++) {/ / f [k - 1]] [j - 1 + 1 broken floor number k - 1 (critical layer can only below) / / f [I - k] [j] + 1 haven't broken the critical layer can only f [I] on [j] = Math.min(f[i][j],Math.max(f[k-1][j-1]+1,f[i-k][j]+1)); } } } return f[lou][dan]; }Copy the codeO (n^2*k)
if(costs==null||costs.length==0||(costs.length==1&&costs[0].length==0)){ return 0; } //costs = rever(costs); int y = costs[0].length; int x = costs.length; int f[][] =new int[x][y]; for(int i=0; i<x; i++){ f[i][0] = costs[i][0]; } for(int j =1; j<y; For (int I =0; int I =0; int I =0; i<x; i++){ int res=Integer.MAX_VALUE; // add k for(int k =0; k<x; k++){ if(k! =i){ res = Math.min(res,f[k][j-1]); } } f[i][j]=res+costs[i][j]; } } int res =Integer.MAX_VALUE; for(int i=0; i<x; i++){ res=Math.min(f[i][y-1],res); } return res;Copy the code###5 Interval partition decoding problem leetCode91 O (n)
public static int solve(String s){
int n = s.length(); If (s.char (0)-'0'==0){return 0; } if(n==1&&s.charAt(0)-'0'! =0){ return 1; } int[] f =new int[n]; if(s.charAt(n-1)-'0'==0&&s.charAt(n-2)-'0'>2){return 0; } f[0]=1; if(s.charAt(0) - '0'>2&&s.charAt(1) - '0'==0){ return 0; }else if(s.charAt(0)-'0'>2||s.charAt(1)-'0' ==0||s.charAt(0) - '0'==2&&s.charAt(1) - '0'>6) { f[1]=1; }else { f[1] =2; } for (int i = 0; i < n; i++) { if(i+1<n&&s.charAt(i)-'0'==0&&s.charAt(i+1)-'0'==0){ return 0; } } for(int i = 2; i<n; i++){Copy the code// How to convert a char to an int instead of its ASCII counterpartCopy the code if(s.charAt(i-1) - '0'>2&&s.charAt(i) - '0'==0){
return 0;
}
if(s.charAt(i-1) - '0'>2||s.charAt(i-1)-'0'==0||s.charAt(i-1) - '0'==2&&s.charAt(i) - '0'>6){
f[i] = f[i-1];
}else if(s.charAt(i)-'0'==0) {
f[i] = f[i-2];
}else{
f[i] = f[i-1]+f[i-2];
}
}
return f[n-1];
Copy the code}
###6 Longest ascending subsequence leetCode300 o (n^2)
public int lengthOfLIS(int[] nums) {
int n =nums.length; if(n==0){ return 0; } int[] f = new int[n]; f[0] =1; for(int i= 1; i<n; i++){ f[i] = 1; for(int j=0; j<i; j++){ if(nums[i]>nums[j]){ f[i] = Math.max(f[j]+1,f[i]); } } } int res =Integer.MIN_VALUE; for (int i = 0; i < n; i++) { res = Math.max(res,f[i]); } return res; }Copy the codeLeetcode64 o (n^2)
public static int findpath(int[][] M){
if(M==null){ return 0; } int x = M.length; int y = M[0].length; int[][] f = new int[x][y]; f[0][0] = M[0][0]; for(int i = 1; i<x; i++){ f[i][0] = M[i][0]+f[i-1][0]; } for(int j =1; j<y; j++){ f[0][j] = f[0][j-1]+M[0][j]; } for (int i = 1; i < x; i++) { for(int j =1; j<y; j++){ f[i][j] = Math.min(f[i-1][j],f[i][j-1])+M[i][j]; } } return f[x-1][y-1];Copy the code}
###8 Given the number n, find the number from 0 to n in base 2 that contains 1
//10to2:Integer.toBinaryString(int i) //2to10:Integer.valueOf("0101",2) public static void onebits(int N){ int[] f = new int[N+1]; f[0] = 0; f[1] = 1; for(int i =2; i<N+1; i++){ String str = Integer.toBinaryString(i); int n = str.length(); if(str.charAt(n-1)=='0'){ f[i] = f[Integer.valueOf(str.substring(0,n-1),2)]; }else { f[i] = f[Integer.valueOf(str.substring(0,n-1),2)]+1; } } for (int i = 0; i < N+1; i++) { System.out.println(f[i]); }} optimization: public static void onebits(int N){ //10to2:Integer.toBinaryString(int i) //2to10:Integer.valueOf("0101",2) int[] f = new int[N+1]; f[0] = 0; f[1] = 1; for(int i =2; i<N+1; F [I] = f[I >>1] + I &1; f[I] = f[I >>1] + I &1; } for (int I = 0; i < N+1; i++) { System.out.println(f[i]); }}Copy the codeFind the number of 1’s in binary
public static int numberOf1(int n){
int count = 0; while(n! =0){ if((n&1) ! = 0){ ++count; } n = n >> 1; } return count; }Copy the codeGiven an array, find the maximum area
public static int findmian(int[] height){
int n =height.length;
int index_1 = 0;
int index_2 = n-1;
int res = 0;
while(index_1<index_2){
res = Math.max((index_2-index_1)*Math.min(height[index_1],height[index_2]),res);
if(height[index_1]<height[index_2]){
index_1++;
}else {
index_2--;
}
}
return res;
Copy the code}
###10 Leetcode198
public static int dajia(int[] nums){
if(nums.length==0||nums==null){
return 0;
}
int n = nums.length;
if(n==1){
return nums[0];
}
int[] f= new int[n];
f[0] =nums[0];
f[1] =Math.max(nums[0],nums[1]);
for (int i = 2; i < n; i++) {
f[i] =Math.max(f[i-2]+nums[i],f[i-1]);
}
return f[n-1];
Copy the code}
### 2 LeetCode213
public static int dajia2(int[] nums) {
if (nums.length == 0 || nums == null) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
if (n == 2) {
return Math.max(nums[0], nums[1]);
}
if (n == 3) {
return Math.max(nums[0],Math.max(nums[1],nums[2]));
}
int[] f = new int[n];
f[0] = nums[0];
f[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n - 1; i++) {
f[i] = Math.max(f[i - 2] + nums[i], f[i - 1]);
}
int f1 = f[n - 2];
f[0] = 0;
f[1] = nums[1];
for (int i = 2; i < n; i++) {
f[i] = Math.max(f[i - 2] + nums[i], f[i - 1]);
}
int f2 = f[n - 1];
return Math.max(f1, f2);
Copy the code}
###12 Backpack problem leetcode1049
Given a bunch of arrays, sum is the closest to the maximum value. The weight dimension is sum and the value dimension is the length of the array. The value and weight arrays share one.
public static int stone2(int [] stones){ if(stones.length==0||stones==null){ return 0; } if(stones.length ==1){ return stones[0]; } int n = stones.length; int sum =0; for (int stone : stones) sum += stone; int weight = sum/2; int[][] f = new int[n][weight+1]; f[0][0] = 0; for (int i = 0; i < n; i++) { f[i][0] = 0; } for (int i = 0; i <weight+1; i++) { if(i>=stones[0]){ f[0][i] = stones[0]; }else { f[0][i] = 0; } } for (int i = 1; i < n; i++) { for(int j =1; j<weight+1; j++){ if(j>=stones[i]){ f[i][j] = Math.max(f[i-1][j-stones[i]]+stones[i],f[i-1][j]); }else{ f[i][j] = f[i-1][j]; } } } int res = sum-2*f[n-1][weight]; return res; }Copy the codeGood code
public int lastStoneWeightII(int[] stones) {
int n = stones.length; int sum = 0; for (int stone : stones) sum += stone; int capacity = sum / 2; int[][] dp = new int[n + 1][capacity + 1]; For (int I = 1; i <= n; I++) {// enumerate stone for (int j = 1; j <= capacity; J++) {/ / enumeration capacity if (stones] [I - 1 > j) {/ / current stone weight is greater than the knapsack capacity not put dp [I] [j] = dp [I - 1) [j]; Dp [I][j] = Math. Max (dp[i-1][j], stones[i-1] + dp[i-1][j-stones [i-1]]); } } } return sum - 2 * dp[n][capacity]; }Copy the codeKnowledge learned
public static int stone(int[] stones){ Queue<Integer> stoneweight = new PriorityQueue<Integer>(idComparator); } // How to define the form of the priority queue, which defaults from small to large, Public static Comparator<Integer> idComparator=new Comparator<Integer>() {public int compare(Integer c1, Integer c2) { return (c2-c1); }};Copy the code###13 Stock trading time leetcode63
public static int gupiao(int[] prices){
int n = prices.length;
if(n==0||prices==null||n==1){
return 0;
}
int[] f =new int[n];
f[0] = 0;
if(prices[0]>prices[1]){
f[1] = 0;
}else {
f[1] = prices[1]-prices[0];
}
for (int i = 2; i < n; i++) {
f[i] = f[i-1]+prices[i]-prices[i-1];
if(f[i]<0){
f[i] = 0;
}
}
int max= 0;
for (int i = 0; i < n; i++) {
max = Math.max(max,f[i]);
}
return max;
Copy the code}
Leetcode122 can be traded multiple times
public static int gupiaonum(int[] prices){
int n = prices.length;
if(n==0||prices==null||n==1){
return 0;
}
int res =0;
for (int i = 0; i <n-1 ; i++) {
if(prices[i+1]>prices[i]){
res+=prices[i+1]-prices[i];
}
}
return res;
Copy the code}
###15 stock trading time n^2(actually nm did not pass, other look not understand
public static int gupiaolirun(int[] prices,int start,int end){
int a = start;
int b =0;
int[] price1 =new int[end-start+1];
while(b<end-start+1){
price1[b++] = prices[a++];
}
int n = price1.length;
if(n==0||price1==null||n==1){
return 0;
}
int[] f =new int[n];
f[0] = 0;
if(price1[0]>price1[1]){
f[1] = 0;
}else {
f[1] = price1[1]-price1[0];
}
for (int i = 2; i < n; i++) {
f[i] = f[i-1]+price1[i]-price1[i-1];
if(f[i]<0){
f[i] = 0;
}
}
int max= 0;
for (int i = 0; i < n; i++) {
max = Math.max(max,f[i]);
}
return max;
Copy the code}
public static int gupiao(int[] prices){
int n = prices.length; if(n==0||prices==null||n==1){ return 0; } if(n==2){ return Math.max(0,prices[1]-prices[0]); } int res =0; for(int k=1; k<n-1; k++){ int left = gupiaolirun(prices,0,k); int right =gupiaolirun(prices,k,n-1); res =Math.max(res,left+right);Copy the code}
return res;
}
Stock trading time 4 can be solved 3, leetcode188
I learned
ArrayList<Integer> price1 =new ArrayList<Integer>();
sum=price1.get(1);
Copy the codeThe problem solving
public static int gupiao4(int k,int[] prices) {
int n = prices.length; if(n==0||prices==null||n==1||k==0){ return 0; } if(n==2){ return Math.max(0,prices[1]-prices[0]); } if(k>n/2){int res =0; for (int i = 0; i <n-1 ; i++) { if(prices[i+1]>prices[i]){ res+=prices[i+1]-prices[i]; } } return res; Int [][] f = new int[n][2 * k + 1]; int[] f = new int[n][2 * k + 1]; for (int i = 0; i < n; i++) { f[i][0] = 0; } for (int i = 0; i < 2 * k+1; i++) { f[0][i] = 0; } for (int i = 1; i < n; i++) { for (int j = 1; j < 2 * k+1; j++) { if ((j & 1) == 1) { f[i][j] = Math.max(f[i - 1][j] + prices[i] - prices[i - 1], f[i - 1][j - 1]); } else { f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - 1] + prices[i] - prices[i - 1]); } } } int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 2 * k+1; j++) { if ((j & 1) == 0){ res = Math.max(res, f[i][j]); } } } return res;Copy the code}
Leetcode354, it is recommended not to call the function, dp conditions are difficult to change, easy to fall into greedy strange game
public int maxEnvelopes(int[][] envelopes) {
int n =envelopes.length; if(n==0||envelopes==null){ return 0; } if(n==1){ return 1; } Comparator<int[]>comp = 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]; }}}; Arrays.sort(envelopes,comp); int[] dp = new int[n]; dp[0] =1; int res =Integer.MIN_VALUE; for(int i= 1; i<n; i++){ dp[i] = 1; for(int j=0; j<i; j++){ if(envelopes[i][1]>envelopes[j][1]&& envelopes[i][0] > envelopes[j][0]){ dp[i] = Math.max(dp[j]+1,dp[i]); } } res = Math.max(res,dp[i]); } return res; }Copy the codeFinding a number can be written at least as the sum of several perfect squares.
public static int numSquare(int n){
int[] f =new int[n+1]; f[0] = 0; f[1] = 1; for (int i =2; i<=n; i++){ f[i] =Integer.MAX_VALUE; for (int j = 1; (j*j) <=i; j++) { f[i] = Math.min(f[i],f[i-j*j]+1); } } return f[n];Copy the code}
Find the minimum number of substrings a string can be divided into
public int minCut(String s) {
int n = s.length();
if(n==0||n==1||s==null){
return 0;
}
int[] f =new int[n];
f[0] = 0;
for (int i = 1; i <n ; i++) {
f[i] =Integer.MAX_VALUE;
for (int j = 0; j <=i; j++) {
if(huiwenfou(s.substring(j,i+1))){
if(j-1<0){
f[i] = 0;
}else {
f[i] = Math.min(f[i],f[j-1]+1);
}
}
}
}
return f[n-1];
}
public boolean huiwenfou(String s){
String reverse = new StringBuffer(s).reverse().toString();
if(s.equals(reverse)){
return true;
}
return false;
}
Copy the code###20 The longest string leetcode05
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) { return ""; } int n = s.length(); boolean[][] f = new boolean[n][n]; f[0][0] = true; for(int j=1; j<n; j++){ for(int i =0; i<=j; i++){ if(i==j){ f[i][j]=true; }else if(i+1==j){ if (s.charAt(i)==s.charAt(j)){ f[i][j] =true; }else { f[i][j] = false; } }else if(i+1<=j-1){ if(f[i+1][j-1]==true&&s.charAt(i)==s.charAt(j)){ f[i][j] = true; }else { f[i][j] = false; } } } } int max =Integer.MIN_VALUE; String aa = ""; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if(f[i][j]==true){ max =Math.max(max,j-i+1); if(j-i+1==max){ aa = s.substring(i,j+1); } } } } return aa;Copy the code}
Find the number of substring leetCode647 in a string
class Solution {
public int countSubstrings(String s) { if (s == null || s.length() == 0) { return 0; } int n = s.length(); boolean[][] f = new boolean[n][n]; f[0][0] = true; for(int j=1; j<n; j++){ for(int i =0; i<=j; i++){ if(i==j){ f[i][j]=true; }else if(i+1==j){ if (s.charAt(i)==s.charAt(j)){ f[i][j] =true; }else { f[i][j] = false; } }else if(i+1<=j-1){ if(f[i+1][j-1]==true&&s.charAt(i)==s.charAt(j)){ f[i][j] = true; }else { f[i][j] = false; } } } } int num = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if(f[i][j]==true){ num++; } } } return num; }Copy the code}
It is possible to take one or two stones from one side — to win is to have a situation in which the other side will lose
public static boolean boyi(int n){
if(n==0){ return false; } boolean[] f =new boolean[n+1]; f[0] = false; f[1] = true; f[2] = true; for(int i =3; i<n+1; i++){ if(f[i-1]==true&&f[i-2]==true){ f[i] = false; }else { f[i] =true; } } return f[n];Copy the code}
###23 Change the minimum number of coins needed to make up the total amount leetcode332
public static int coinChange(int[] coins, int amount){
int n =coins.length;
if(amount==0){
return 0;
}
if(n==0||coins==null||amount==0){
return -1;
}
Arrays.sort(coins);
int[] f =new int[amount+1];
f[0] = 0;
for (int i = 1; i < amount+1; i++) {
f[i] =0x3f3f3f3f;
for (int j = 0; j < n; j++) {
if(i>=coins[j]){
f[i] = Math.min(f[i-coins[j]]+1,f[i]);
}
}
}
return f[amount] == 0x3f3f3f3f ? -1 : f[amount];
Copy the code}
###24 Given an array, find N not more than N can make up the largest number of 0-1 knapsack 1-dimensional solution
public static int stonexin(int[]ss,int n){
int m =ss.length;
boolean[] f =new boolean[n+1];
f[0] = true;
for (int i = 0; i <n+1 ; i++) {
for (int j = 0; j < m; j++) {
if(i>=ss[j]){
f[i] = f[i]||f[i-ss[j]];
}
}
}
int max =Integer.MIN_VALUE;
for (int i = 0; i < n+1; i++) {
if(f[i]==true){
max =Math.max(max,i);
}
}
return max;
Copy the code}
Knapsack problem general solution
F [I][w] =f[i-1][w] or f[i-1][w-a [I]]
###25 Book coin 2leetcode518 two-dimensional writing
class Solution {
public int change(int amount, int[] coins) {
int n =coins.length;
if(amount==0){
return 1;
}
if(n==0||coins==null){
return 0;
}
int[][] f =new int[n][amount+1];
for (int i = 0; i < n; i++) {
f[i][0] =1;
}
for (int j = 1; j < amount+1; j++) {
for (int i = 0; i < n; i++) {
if(i==0){
if(j%coins[i]==0){
f[i][j] =1;
}
}else {
if(j>=coins[i]){
f[i][j] = f[i-1][j]+f[i][j-coins[i]];
}else {
f[i][j] = f[i-1][j];
}
}
}
}
return f[n-1][amount];
}
Copy the code}
A one-dimensional writing
public static int coins(int amount,int[] coins){
int n =coins.length;
if(amount==0){
return 1;
}
if(n==0||coins==null){
return 0;
}
int[] f =new int[amount+1];
f[0] =1;
for (int j = 0; j < n; j++) {
for (int i = coins[j]; i <amount+1 ; i++) {
f[i] += f[i-coins[j]];
}
}
return f[amount];
Copy the code}
###26 Longest sequence of subrons
public static int huiwenzixulie(String s){
int n = s.length();
if(n==1){
return 1;
}
int[][] f =new int[n][n];
int max =0;
f[0][0] =1;
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
f[j][j] = 1;
if(s.charAt(i)==s.charAt(j)){
f[i][j] = f[i+1][j-1]+2;
}else {
f[i][j] = Math.max(f[i+1][j],f[i][j-1]);
}
max = Math.max(f[i][j],max);
}
}
return max;
Copy the code}
###27 Game Theory Take stones left and right (f array – maximum score from I to j)
public static boolean stoneGameII(int[] piles){
int n = piles.length;
if(n==0||piles==null){
return true;
}
int[][] f = new int[n][n];
f[0][0] = piles[0];
int sum = piles[0];
for (int j = 1; j < n; j++) {
sum += piles[j];
f[j][j] = piles[j];
for (int i = 0; i < j; i++) {
f[i][j] = Math.max(piles[i] - f[i+1][j],piles[j] - f[i][j-1]);
}
}
if(f[0][n-1] > 0){
return true;
}
return false;
Copy the code}
# # # 28 dichotomy
public static int search(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n-1;
while(left<right){
int mid =left+((right-left)>>1);
if(nums[mid]<target){
left = mid+1;
}else {
right = mid;
}
}
return left;
}
Copy the code# # # 35 cut the rope
public int cuttingRope(int n) {
if(n==2)return 1;
if(n==3)return 2;
int[] f = new int[n+1];
f[0] = 0;
f[1] = 1;
f[2] = 2;
for (int i = 3; i < f.length; i++) {
f[i] = i;
for (int j = 1; j < i; j++) {
f[i] = Math.max((i-j)*f[j],f[i]);
}
}
return f[f.length-1];
}
Copy the code### Dichotomous variation
public boolean search(int[] nums, int target) {
int l =0,r=nums.length-1;
while(l<=r){
int mid = l+(r-l)/2;
if(nums[mid]==target)return true;
else if(nums[l]<nums[mid]){
if(nums[l]<=target && target<nums[mid])r=mid-1;
else l=mid+1;
}
else if(nums[l]>nums[mid]){
if(nums[r]>=target && target>nums[mid])l=mid+1;
else r=mid-1;
}
else l++;
}
return false;
}
Copy the code### Covet minimum interval number
public int findMinArrowShots(int[][] points) {
if(points.length < 1) return 0;
Arrays.sort(points, (Comparator.comparingInt(o -> o[1])));
int count = 1;
int axis = points[0][1];
for(int i = 1; i < points.length; ++i) {
if(axis < points[i][0]) {
count++;
axis = points[i][1];
}
}
return count;
}
Copy the code