动态规划 由简单到难

  1. 爬楼梯问题

    每次可以爬1或2个台阶 爬到第10层有几种办法

    climb = lambda x: climb(x-1) + climb(x-2) if x > 2 else x
    

另一种实现

```
def climb(n):
    temp = [1, 2]
    for i in range(3, n+1):
        temp[i%2] = sum(temp)
    return temp[n%2]
```
  1. 小偷

    你是⼀个专业的⼩偷,计划偷窃沿街的房屋。每间
    素就是相邻的房屋装有相互连通的防盗系统,如果
    动报警。
    给定⼀个代表每个房屋存放⾦额的⾮负整数数组,
    最⾼⾦额。

    输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3
    偷窃到的最高金额 = 1 + 3 = 4 。
    输入: [2,7,9,3,1]
    输出: 12
    解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房
    1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
    

    答案

    def rob(nums):
        last, now = 0, 0
        for i in nums: last, now = now, max(last + i, now)
        return now
    

    golang实现

    package main
    
    import "fmt"
    
    func rob(nums []int) int {
        last, now := 0, 0
        for _, value := range nums{
            var tmp int = last + value
            if tmp < now {
                tmp = now
            }
            last, now = now, tmp
        }
        return now
    }
    
    func main(){
        fmt.Println(rob([]int{1, 2, 3, 1}))
        fmt.Println(rob([]int{2, 7, 9, 3, 1}))
    }
    
  2. 数字字母匹配

    题目: 有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'。现在给一串数字,给出有多少种可能的译码结果

    def num_decoding(s):
        last, now = 1, int(s[0] != '0')
        for i in range(1, len(s)):
            last, now = now, last * (9 < int(s[i - 1:i + 1]) <= 26) + now * (int(s[i]) > 0)
        return now
    

    提示 要注意 0, 10, 101这种带0的

  3. 青蛙过河普通版

    在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是s到t之间的任意正整数(包括s,t)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

    题目给出独木桥的长度L,青蛙跳跃的距离范围s,t,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

    def jump(s, t, l):
        """
    
        :param s: s > 0
        :param t: t > s
        :param l: l 第一个位置永远是0 最后是终点
        :return:
        """
        d = {x: False for x in l}
        d[0] = True
    
        for k in l:
            if d[k]:
                for step in range(s, t+1):
                    if k+step in d:
                        d[k+step] = True
                    if k + step >= l[-1]:
                        return True
        return False
    
    print(jump(1, 2, [0, 2, 3, 5]))
    print(jump(1, 2, [0, 2, 3, 6]))
    print(jump(1, 2, [0, 3, 4, 5]))
    print(jump(1, 3, [0, 2, 3, 6]))
    
  4. 青蛙过河最终版

    题目:一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。

    给定石子的位置列表(用单元格序号升序表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格1跳至单元格2)。

    如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。

    请注意:

    石子的数量 ≥ 2 且 < 1100;
    每一个石子的位置序号都是一个非负整数,且其 < 231;
    第一个石子的位置永远是0。

    思路:

    在动态规划方法中,我们会利用散列表 mapmap,对于散列表中的 key:valuekey:value,keykey 表示当前石头的位置,valuevalue 是一个包含 jumpsizejumpsize 的集合,其中每个 jumpsizejumpsize 代表可以通过大小为 jumpysizejumpysize 的一跳到达当前位置。首先我们对散列表初始化,keykey 为所有石头的位置,除了位置 0 对应的 valuevalue 为包含一个值 0 的集合以外,其余都初始化为空集。接下来,依次遍历每个位置上的石头。对于每个 currentPositioncurrentPosition,遍历 valuevalue 中每个 jumpsizejumpsize,判断位置 currentPosition + newjumpsizecurrentPosition+newjumpsize 是否存在于 mapmap 中,对于每个 jumpsizejumpsize,newjumpsizenewjumpsize 分别为 jumpsize-1jumpsize−1,jumpsizejumpsize,jumpsize+1jumpsize+1。如果找到了,就在对应的 valuevalue 集合里新增 newjumpsizenewjumpsize。重复这个过程直到结束。如果在结束的时候,最后一个位置对应的集合非空,那也就意味着我们可以到达终点,如果还是空集那就意味着不能到达终点。

    官方答案

    public class Solution {
        public boolean canCross(int[] stones) {
            HashMap<Integer, Set<Integer>> map = new HashMap<>();
            for (int i = 0; i < stones.length; i++) {
                map.put(stones[i], new HashSet<Integer>());
            }
            map.get(0).add(0);
            for (int i = 0; i < stones.length; i++) {
                for (int k : map.get(stones[i])) {
                    for (int step = k - 1; step <= k + 1; step++) {
                        if (step > 0 && map.containsKey(stones[i] + step)) {
                            map.get(stones[i] + step).add(step);
                        }
                    }
                }
            }
            return map.get(stones[stones.length - 1]).size() > 0;
        }
    }
    
    
原文地址:https://www.cnblogs.com/wangjiale1024/p/10403096.html