1.硬币问题 

public int ways(int []nums,int target){        int[]dp=new int[target+1];        //dp[i]表示和为i有多少种组合        dp[0]=1;        for(int i=0;i<=target;i++)            for(int n:nums){                if(n+i<=target)                    dp[n+i]+=dp[i];            }        return dp[target];    }

简单递归

int count(int[]nums,int sum,int tar){        int res=0;        if(sum

2.LCS

int lcs(String a,String b){        int lena=a.length(),lenb=b.length();        int [][]dp=new int[lena+1][lenb+1];        //dp[i][j]表示a的前i个和b的前j个的LCS        for(int i=1;i<=lena;i++)            for(int j=1;j<=lenb;j++)                if(a.charAt(i-1)==b.charAt(j-1))                    dp[i][j]=dp[i-1][j-1]+1;                else                    dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j]);        return dp[lena][lenb];    }

3.0-1背包

public int ways(int c){        int packets=w.length;        int [][]dp=new int[packets+1][c+1];        for(int i=1;i<=packets;i++)            for(int j=0;j<=c;j++){                if(j==0)                    dp[i][j]=0;                else if(j>=w[i-1]){                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i-1]]+p[i-1]);                }else                    dp[i][j]=dp[i-1][j];            }        return dp[packets][c];    }

空间优化后：

public int ways2(int c){        int packets=w.length;        int []dp=new int[c+1];        for(int i=1;i<=packets;i++)            for(int j=c;j>=0;j--)                if(j>=w[i-1])                    dp[j]=Math.max(dp[j], dp[j-w[i-1]]+p[i-1]);        return dp[c];    }

简单递归

public int solve(int i,int n,int j,int max){        if(i
      
       =w[i]){                return Math.max(solve(i+1,n,j-w[i],max+p[i]),solve(i+1,n,j,max));            }else{                return solve(i+1,n,j,max);            }            }else            return max;    }
      

3.多重背包

public int packetK(int c){        int [][]dp=new int[w.length+1][c+1];        for(int i=1;i<=w.length;i++)            for(int j=0;j<=c;j++)                if(j==0)                    dp[i][j]=0;                else if(j

4.最长非降序子序列 类似 

//最长非降序子数列    public int MaxUnDESCSub(int []nums){        int []dp=new int[nums.length];        //dp[i]为0..i不降序的最大字串长度        Arrays.fill(dp, 1);        for(int i=1;i
     
      =nums[j]&&dp[i]<=dp[j])                    dp[i]=dp[j]+1;            }        }        Arrays.sort(dp);        return dp[nums.length-1];    }
     

5.爬台阶

public int ways(int n){        int []dp=new int[n+1];        dp[1]=1;dp[2]=1;        for(int i=3;i<=n;i++)            dp[i]=dp[i-1]+dp[i-2];        return dp[n];        }

6.（前缀思想 

public int maxBlancedSub(String s){        /*         *前缀和思想 连续性         *dp[i]表示前i个数 */        int len=s.length();        int []dp=new int[len+1];        for(int i=1;i<=len;i++)            if(s.charAt(i-1)=='0')                dp[i]=dp[i-1]-1;            else                dp[i]=dp[i-1]+1;        HashMap
     
      map=new HashMap<>();        int max=0,begin=0;        for(int i=1;i<=len;i++){            if(map.containsKey(dp[i]))                begin=map.get(dp[i]);            else                map.put(dp[i], i);            if(dp[i]==dp[begin]&&i-begin>max)                max=i-begin;        }        return max;    }
     

 7.图论问题

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {          int [][]dp=new int[n][k+1];          int [][]f=new int[n][n];          for(int i=0;i
     
      =0)                      dp[i][j]=f[src][i];                  else if(j>0){                      for(int m=0;m
      
       0&&dp[m][j-1]!=Integer.MAX_VALUE)                              dp[i][j]=Math.min(dp[m][j-1]+f[m][i], dp[i][j]);                  }              }          }          Arrays.sort(dp[dst]);          if(dp[dst][0]!=Integer.MAX_VALUE)              return dp[dst][0];          return -1;      }
      
     

 

8.

public int numTrees(int n) {       int []dp=new int[n+1];       for(int i=1;i<=n;i++){           if(i==1||i==2)               dp[i]=i;           else{               for(int j=1;j<=i;j++)                   if(j>1&&j