python算法技巧——动态规划算法练习及掌握

r囧r小猫 2023-09-29 13:01 75阅读 0赞

**目录**

1. 处理爬楼梯的问题

2. 募捐基金问题

3. 最小经费粉刷房子问题

4. 篱笆粉刷方法数量问题

5. 机器人在地图上的路径走法问题

6. 背包问题

--------------------

#### **1. 处理爬楼梯的问题** ####

> 设计climbstairs(n)进行处理，参数n代表n阶楼梯，每次可以爬1或2阶楼梯，得出有几种爬法可以爬上顶楼；

def  climbstairs(n):
        prev, cur = 1, 1
        for i in range(1, n):
            prev, cur = cur, prev+cur
        return cur
    print(climbstairs(2))
    print(climbstairs(4))

--------------------

#### **2. 募捐基金问题** ####

> 设计col(nums)函数计算最多可以募捐多少价值的物品，在募捐时不可以拜访连续的房子；

def col(nums):
        prev = cur = 0
        for money in nums:
            prev, cur = cur, max(prev+money, cur)
        return cur
    print(col([1,2,3,1]))
    print(col([2,7,9,3,1]))

--------------------

#### **3. 最小经费粉刷房子问题** ####

> 设计mincost(costs)，由于粉刷房子有red、blue、green三种颜色，没见房子粉刷不用颜色会有不同的价格，同时所有相邻的房子不可以刷相同的颜色；
> 
> 粉刷房子的颜色用数组表示，参数costs是相关信息，如：costs\[0\]\[0\]指的是房子0粉刷红色的费用；

def mincost(costs):
        red = 0
        blue = 0
        green = 0
        for r,b,g in costs:
            red, blue, green = r+min(blue,green), b+min(red,green), g+min(red,blue)
        return min(red,blue,green)
    print(mincost([[17,2,14],[15,16,5],[14,3,18]]))

--------------------

#### **4. 篱笆粉刷方法数量问题** ####

> 设计numways(n,k)，参数n代表篱笆数量，k代表油漆颜色数量，在粉刷时不可以有超过连续两个篱笆使用相同颜色；

def numways(n,k):
        if n==0:
            return n
        if n==1:
            return k
        same = k
        diff = k*(k-1)
        for i in range(3,n+1):
            same, diff = diff, (same+diff)*(k-1)
        return same+diff
    print(numways(4,2))

**代码解读：**

> 对于这个程序，首先的n=0和1的情况应该不用多说，而当n=2时，有两种情况：
> 
>  *  和前一个篱笆相同，有k\*1种方法，此时我们的变量名定为same；
>  *  和前一个篱笆不相同，有k\*(k-1)种方法，此时我们的变量名定为diff；
> 
> 而当n>=3时，因为有条件限制不可以有超过两种颜色相同，所以可以如下分析：
> 
>  *  下一个篱笆绘制相同颜色的变量计算方式为：same=diff；
>  *  绘制不同颜色的变量计算方式为：diff = (same+diff)\*(k-1)
> 
> 最后我们只需要回传same+diff的总和就好了；

--------------------

#### **5. 机器人在地图上的路径走法问题**  ####

> 设计uniquepaths(m,n)记录机器人邹尼地图上的左上角到地图右下角有几种走法，参数m是地图方格的row，参数n是地图方格的column，机器人的起点是在地图(0,0)位置，机器人的终点是在地图上(m-1,n-1)位置；
> 
> 且机器人只可以往右走或是往下走，求共有多少种走法：

def uniquepaths(m,n):
        map = [[0 for i in range(n)]for j in range(m)]
        for i in range(m):
            for j in range(n):
                if i==0 or j==0:
                    map[i][j]=1
                else:
                    map[i][j] = map[i-1][j]+map[i][j-1]
        return map[m-1][n-1]
    print(uniquepaths(3,2))
    print(uniquepaths(7,3))

> 这个程序是使用了map二维数组记录机器人有多少种走法，记录方法如下：
> 
>  *  凡是row=0或column=0，表示走法只有一种；
>  *  其他方格的走法则是“左边方格的走法”+“上方方格的走法之和”；

--------------------

#### **6. 背包问题** ####

> 一个人有一个可以装10千克货物的背包，他到一个市场想最大价值的带走他想要的东西，请你用贪心算法帮他：
> 
>  *  item = \['手表','手机','平板','电脑','相机','眼镜','耳机'\]
>  *  value = \[1500, 3500, 3800, 4000, 2000, 1200, 1000\]
>  *  weight\_things = \[2, 4, 5, 8, 3, 1, 1\]

def bag(w, wt, val):
        n = len(val)
        table = [[0 for x in range(w+1)] for x in range(n+1)]
        items = [[[]for x in range(w+1)] for x in range(n+1)]
        for r in range(n+1):
            for c in range(w+1):
                if r==0 or c==0:
                    table[r][c] = 0
                elif wt[r-1] <= c:
                    cur = val[r-1] + table[r-1][c-wt[r-1]]
                    cur_items = []
                    cur_items.append(item[r-1])
                    if items[r-1][c-wt[r-1]]:
                        cur_items += items[r-1][c-wt[r-1]]
                    pre = table[r-1][c]
                    pre_items = items[r-1][c]
                    if cur > pre:
                        table[r][c] = cur
                        items[r][c] = cur_items
                    else:
                        table[r][c] = pre
                        items[r][c] = pre_items
                else:
                    table[r][c] = table[r-1][c]
                    items[r][c] = items[r-1][c]
        return items, table[n][w]
    
    
    item = ['手表','手机','平板','电脑','相机','眼镜','耳机']
    value = [1500, 3500, 3800, 4000, 2000, 1200, 1000]
    weight_things = [2, 4, 5, 8, 3, 1, 1]
    bag_weight = 10
    items, total_value = bag(bag_weight, weight_things, value)
    print('最大价值为：', total_value)
    print('商品组合为:', items[len(item)][bag_weight])

--------------------

## **算法技巧专栏** ##

[https://blog.csdn.net/weixin\_53919192/category\_11761989.html![icon-default.png_t_M3K6][]https://blog.csdn.net/weixin\_53919192/category\_11761989.html][https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]

[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]: https://blog.csdn.net/weixin_53919192/category_11761989.html