新しいピットLeet Code DP(ダイナミックプランニング)の問題解の合計

卒業して年を取って、新しい穴を掘って、同級生は1つのLeet Code OJを推薦して私にあげて、前にACMをして私はDP問題をするのが一番好きで、だから新しいOJに対して、私が言いたいのは、DP問題は私に任せましょう.问题の问题解は顺番がなくて、ある问题を调べて自分で検索することができて、私はまだ解决していない伝言を残して私に解决するように注意することができます.ちなみに今回の問題はJAVAでやるつもりです.
P303. Range Sum Query - Immutable
問題解:問題の大きい1は1つの配列を与えて、いくつかの問題を与えて、私達に区間とを求めさせて、もしO(n^2)の方法を使うならばとても直観的で、しかし効率は高くなくて、実は私達は1つの前処理をするだけで、すべての問題はO(1)の時間内に解くことができます.Range(i,j)=Sum[j]-sum[i-1]{sum[i]は配列の最初の数の和であるからである.したがって,前処理は配列の前数和を行う過程である.全体的に簡単な問題です.
参照コード:

public class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
      int l=nums.length;
      if(l!=0){
      sum=new int[l];
      sum[0]=nums[0];
      for(int i=1;i

P368. Largest Divisible Subset
問題解:問題の大意は非負の数字の集合で、重複する数字はありません.最も長いサブセットを求めて、サブセットの任意の2つの数が大きい数を満たすには小さい数を除去します.基本的なDP問題型は,この問題は時間的複雑さの要求が高くなく,n(O^2)の方法でACが可能であり,まず配列を並べ替え,dp[i][1]は配列中の前i個数の中で最も長いサブセットを表す.aがbを除去すると、bを除去できる他のすべての数を保証することができるからである.転移方程式は
dp[i][1]=max(dp[i][1],dp[j][1]+1){i%j==0};そしてdp[i][0]は、どのjから移行したのかを記録するために用いられ、答えの集合を出力するのに便利である.詳細はリファレンスコードを参照してください.
参照コード:

public class Solution {
    public static List largestDivisibleSubset(int[] nums) {
      List re=new ArrayList();
      if(nums.length==0) return re;
      if(nums.length==1){
        re.add(nums[0]);
        return re;
      }
      Arrays.sort(nums);
      int l=nums.length;
      int[][] dp=new int[l+1][2];
      dp[0][1]=1; dp[0][0]=-1;
      for(int i=1;idp[i][1]){
          dp[i][1]=dp[j][1]+1;
          dp[i][0]=j;
        }
      } 
      int maxv=0,maxi=0;
      for(int i=0;imaxv){
        maxv=dp[i][1];
        maxi=i;
      }
      while(maxi!=-1){
        re.add(nums[maxi]);
        maxi=dp[maxi][0];
      }
      return re;
    }
}