前言：

leetcode刷题是实力的一种表现。作为刚刷十几题的小白来讲，是真的刷不动。每刷一题，就得花一两个小时（毕竟真的没有天赋），所以掌握刷题技巧是很有必要的。我最近从我同学那得到一武林绝学————动态规划。亲测，高效！！！所以我也想分享给大家。当然也希望大师们能传授一些你们的绝世神功！

src=http___s6.sinaimg.cn_orignal_49dd212b5b65db3f3b755&refer=http___s6.sinaimg.jpg

动态规划

定义

动态规划（Dynamic programming，简称DP）：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划背后的基本思想大致上为：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用

应用

动态规划常常适用于有关重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法

例题1

leetcode 第七十题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶

2 阶

解题思路：

求得是有多少种方法爬上楼，且一步有两种爬法。令arr[n]为爬n阶的方法，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，爬上第n层的方法会等于爬1层的次数加爬2层方法的和。

2. arr[n-1]为到达n-1阶的方法数，arr[n-2]为到达n-2阶的方法。所以arr[n]就会等于到达n-1阶的方法数与n-2阶方法数之和，即 arr[n]=arr[n-1]+arr[n-2]。
3. 依次类推 arr[n-1]=arr[n-2]+arr[n-3]、arr[n-2]=arr[n-3]+arr[n-4]……arr[2]=arr[1]+arr[0]。
学废了吗，这就是动态规划！

将n阶楼梯分为若干段。又因为是从第0阶开始爬的，所以从第 0 阶爬到第 0 阶我们可以看作只有一种方案，即 arr[0]=1,从第 0 阶到第 1 阶也只有一种方案，即爬一级，arr[1]=1。
代码实现如下：

 var climbStairs = function(n) {
    let arr=[]//定义数组arr[]，用来存储方法数
    arr[0]=1//第0阶方法为一
    arr[1]=1//上第一阶方法为一
    for(let i=2;i<=n;i++){//从第二阶开始
        arr[i]=arr[i-1]+arr[i-2]//上第i阶的方法数
    }
    return arr[n]
};
复制代码

例题2-难度升级

leetcode 第368题

给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。

示例 1：
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：
输入：nums = [1,2,4,8]
输出：[1,2,4,8]

解题思路：

判断answer[i]%answer[j]==0||answer[j] % answer[i] == 0

这种情况使用两个循环就比较简单了。如果能保证当i < j时，answer[i]< answer[j] 也成立，是不是减轻了点复杂度？又因为只要求返回的数组answer，answer中元素排序不重要，所以可以先将nums从小到大排下序。

保存结果并比较每一次的结果长度，返回最长的即可

若answer[i]为answer整除数组中最大的元素。当nums[j]%nums[i]==0时，就可以将nums[j]也添加到answer数组中。
这时num[j]就是answer整除数组中最大的元素。就这样依次判断nums[j]%nums[i]==0？条件成立就放入answer数组，直至遍历完整个nums数组。最后判断每个结果数组的长度，返回最长的即可。

这就是动态规划，将nums先分成小数组，然后判断条件，小数组添值。

 var largestDivisibleSubset = function(nums) {
    let answer=[] //声明answer数组
    let answerlen=new Array(nums.length)//定义answerlen数组，用来接收每次结果的长度
    let maxIndx=0 //声明maxIndx变量，赋值为每次answer数组中最大值的下标
    nums.sort((a,b)=>(a-b))//将nums数组从小到大排序
    
    for(let i=0;i<nums.length;i++){//i表示answer数组中最大的元素nums[i]的下标
        
        answerlen[i]=1;//每个元素必然至少与自己形成一个子集
        
        for(let j=0;j<i;j++){//j最大的元素nums[i]之前元素的下标
            
            if(nums[i]%nums[j]==0){
                
                answerlen[i]=Math.max(answerlen[i],answerlen[j]+1)
                //answerlen[i]即当nums[i]为answer数组最大元素时，answer数组的长度
                //若判断条件成立，nums[j]也要存入数组answer中，即answerlen[j]+1
                //有可能answerlen[j]+1会小于answerlen[i]（前一次循环得到answer的长度） 此时answerlen取它们之间的最大值
            }
        }
        if(answerlen[i]>answerlen[maxIndx]){//令maxIndex为answer数组长度最大时，answer数组元素最大值的下标
            maxIndx=i
        }
    }   
    //因为之前nus数组最大子集answer为空，只得到最大元素nums[maxIndex]和其长度 answerlen[maxIndex]
    answer.push(nums[maxIndx])//将最大元素放入数组
    for(let i=nums.length-1;i>=0&&answerlen[maxIndx]>1;i--){
        if(answerlen[maxIndx]-1==answerlen[i]&&nums[maxIndx]%nums[i]==0){
            //并不是最大元素之前的元素都能被其整除
            //若条件成立，即将改元素放入数组answer，并令最大元素的下标为此时第二大的元素nums[i]的下标，
            //这使只要比较小于nums[i]的元素即可
            answer.push(nums[i])
            maxIndx=i
        }
    }
    return answer
};
复制代码