动态规划的两个经典例子（面试题）

待我称王封你为后i 2022-05-17 09:35 208阅读 0赞

## 1、 动态规划 ##

动态规划问题是面试题中的热门话题，如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

使用动态规划特征：  
1. 求一个问题的最优解  
2. 大问题可以分解为子问题，子问题还有重叠的更小的子问题  
3. 整体问题最优解取决于子问题的最优解**（状态转移方程）**  
4. 从上往下分析问题，从下往上解决问题  
5. 讨论底层的**边界问题**

## 2、实例1 ##

**剪绳子问题**  
给你一根长度为N的绳子，请把绳子剪成M段（m,n都是整数），每段绳子的  
长度记为k\[0\],k\[1\],k\[2\]…. 请问如何剪绳子使得k\[0\],k\[1\],k\[2\]  
的乘积最大  
例如 绳子长度8 最大乘积18 = 2\*3\*3

def jianshengzi(n):
        # 先对边界问题进行求解，因为明显剪的值小于不剪的值
        # 则提出先讨论这三种情况
        if n < 2:
            return 0
        if n == 2:
            return 1    #长度为2，只能剪成1*1
        if n == 3:
            return 2    #长度为3，剪成2*1 > 1*1*1
    
        #若绳子长于４呢,申请一个长度为50的数组
        #罗列出切割的边界问题
    
        h = [0]*50
        h[0] = 0
        h[1] = 1
        h[2] = 2
        h[3] = 3
        # 递归问题是 f(n) = max{f(i)*f(n-i)}
        for i in range(4,n+1):
            maxs = 0
            for j in range(1,i/2+1):
                mult = h[j] * h[i-j]
                if maxs < mult:
                    maxs = mult
                h[i] = maxs     # 每次J的迭代轮询出该长度的最大值
        print h
        return h[n]
    
    print jianshengzi(8)

## 3、实例2 ##

**硬币问题**   
我们有面值为1元3元5元的硬币若干枚，如何用最少的硬币凑够11元？  
分析：  
1 求问题的最优解：最小的硬币数  
2 是否有子问题：f(n)表示的最少硬币数是是上一次拿时候的硬币数最少。  
注意：f(n)是n元的最小硬币数，最后一次可拿的硬币数为1,3,5 则下一步  
的最小硬币数为 f(n-vi) 它的状态变更不是按元数的，是按照上次拿的硬币钱目  
3 状态转移方程为 f(n)= min(f(n-vi)+1)  
4 边界问题(找到最后一个重复的问题) 这里  
f(1)=1 ,f(2)=f(1)+f(1)=2 f(3)=min(1,f(2)+1)  
f(4)=f(3)+1 f(5)=1  
5 从上往下分析问题，从下往上解决问题。

def f(n):
        if n == 1:      #把所有的边界问题找到
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 1
        if n == 4:
            return 2
        if n == 5:
            return 1
    
        h = [1,3,5]
        minx = n
        for i in range(3):
            coun = f(n-h[i])+1    # 采用了递归的思想 这里是从上到下，
            if minx > coun:       # 复杂度比较高
                minx = coun
        return minx
    
    print f(11)

def f(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 1
        if n == 4:
            return 2
        if n == 5:
            return 1
    
        h = [1,3,5]
        for x in range(6,n+1):     #从下往上的思维解决
            minx = n
            for i in range(3):      
                coun = f(x-h[i])+1   #从下往上的思维解决 
                if minx > coun:
                    minx = coun
        return minx
    print f(11)

转载自：[https://blog.csdn.net/tongxinzhazha/article/details/77407648][https_blog.csdn.net_tongxinzhazha_article_details_77407648]

[https_blog.csdn.net_tongxinzhazha_article_details_77407648]: https://blog.csdn.net/tongxinzhazha/article/details/77407648