引言

实际上我这是第一次真正意义上的接触算法。。。。

  1. 个人观点：DP问题–大规模划分成小规模，—-一种解决问题的思想。不要被固定套路约束
  2. 通过小浩算法的五道题（除去第一道）来理解DP，掌握DP

第一个问题

题目

给你一个长度为n的绳子，请把绳子剪成m段，每段绳子的长度记为K[0],k[1]…..k[m],请问K[0]*…k[n]的最大乘积是多少

动态规划解决

  1. 分析：定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，有n-1种可能，也就是说剪出来的第一段绳子可能的长度1，2，…n-1。因此f(n)=max(f(i)*f(n-i)). 计算自上而下，最优解存储在product矩阵中

  2. 代码如下 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def maxProductAfterCutting_solution(length):  # int类型
        if length<2 : return 0
        if length==2: return 1
        if length==3: return 2
        products = [0 for i  in range(length+1)]
        products[0],products[1],products[2],products[3]=0,1,2,3
        max_mul = 0
        
        for i in range(4,length+1):  # 从4开始求出f(n)的最大值
            max = 0
            for j in range(1,int(i/2)+1):  #一半是因为重复计算
                product = products[j]*products[i-j]  
                if max_mul < product: max_mul =product  #当N=i时的最大值
            products[i] = max_mul  # 打表出，当N等于某个值得时候得最大值
        max_mul  = products[length]
        return max_mul

贪婪算法解决

  1. 分析： n>=5的时候应尽可能多地剪长度为3的绳子，当剩下的绳子长度为n的时候，把绳子剪成两段长度为2的绳子。证明：n>=5时，2(n-2)>n,3(n-3)>n，且3（n-3）>2(n-2) 但是n=4的时候2*2比较da

  2. 代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def maxProductAfterCutting_solution2(length): #int类型
        if(length<2):return 0# 至少剪一次
        if(length==2): return 1
        if(length==3): return 2
        
        temes_3 = int(length/3)  #尽可能剪长度为3的绳子
        
        # 但是绳子长度为4的时候还是2*2大
        if (length-times_3*3)==1: times_3-=1
        times_2 = (length-times_3*3)/2
        return int(pow(3,times_3))*int(pow(2,times_2))

第二个问题

题目

你正在爬楼梯，需要N阶才能到达顶楼，一次可以爬一阶或者两阶，请问有多少种不同的方法爬上去（青蛙。。）

分析

  1. 大问题有小问题的结果产生：上n阶台阶，只能从第n-1阶或者第n-2阶到达第n阶，则上第n阶的方法总数是到第n-1阶和到第N-2阶的方法数之和——-这样就有趣了，可以依次向下分解
  2. dp[n]=dp[n-1]+dp[n-2]

代码

1
2
3
4
5
6
7
8
def climbStairs(n):
    if n==1: return 1
    dp = [0 for i in range(0,n+1)]
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1]+dp[i-2]
    return dp[n]

时间复杂度

貌似o(n*n) 没搞懂 晚上充电这个时间复杂度，现在先写代码

第三个问题

题目

给定一个整数数组nums，找到具有最大和的连续子数组，并返回其最大和

分析

  1. 动态规划第一步是定义状态:一个连续的子数组一定要以一个数作为结尾，定义dp[i]表示以num[i]结尾的连续子数字的最大和
  2. 原因是要得到dp[i]则num[i]一定会被选取，在dp[i-1]大于0的时候，dp[i]所表示的子序列与dp[i-1]表示的连续子序列差一个num[i]
  3. dp[i] = dp[i-1]+nums[i] (dp[i-1]>0)
  4. dp[i]=nums[i] (dp[i-1]<0)
  5. 由此可得出状态转移方程：dp[i]=max[num[i],dp[i-1]+num[i]]
  6. 得到状态转移方程后，需要通过一个已有的状态进行推导
  7. 因为dp[0]一定是以num[0]结尾的，所以对dp[0]进行初始化
  8. 值得注意的是，在很多题目中dp[i]就被定义为题目中的问题，但是本题并不是，
  9. 我们需要寻找的是max(dp[0],dp[1],…,dp[i])

代码

1
2
3
4
5
6
7
8
9
def maxSubArray(nums):  #nums是数组
    if len(nums)<1: return 0
    dp = [0 for i in range(len(nums)+1)]
    result = nums[0]
    dp[0] = nums[0]
    for i in range(1,len(nums)):
        dp[i] = max(dp[i-1]+nums[i],nums[i])
        result = max(dp[i],result)
    return result

第四个问题

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度（LIS）

如：[10,9,2,5,3,7,101,18]则最长是：[2,5,3,7,101]，存在多种则只需输出对应长度即可

最长上升子序列不一定连续

分析

  1. 符合可以从子问题的最优解构建的条件-用动态规划
  2. 定义状态，dp[i]表示以nums[i]结尾的最长上升子序列的长度
  3. 若nums[i]比前面的所有元素都小，则dp[i]=1
  4. 若nums[i]前面存在比他小的元素nuns[j],nums[k]…..则
  5. dp[i]=max(dp[j]+1,dp[k]+1….) （需满足nums[i]>[j],[k]）
  6. 最后我们只需找到dp数组的最大值即可

代码

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLIS(nums):
    if len(nums)<1: return 0
    dp = [0 for i in range(len(nums))]
    result=1;
    for i in range(len(nums)):
        dp[i]=1 
        for j in range(i):
            if nums[j]<nums[i]: dp[i] = max(dp[j]+1,dp[i]) #挨个找
                
        result = max(result,dp[i])
    return result