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

目录

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.htmlhttps://blog.csdn.net/weixin_53919192/category_11761989.html