首页 > itarticle > 动态规划之浅见

动态规划之浅见

admin 11月 01, 2020 0

动态规划

动态规划与分治法相似，都是通过组合子问题的解来求解原问题。

分治法将问题划分为不互相交子问题，递归的求解子问题，再将他们组合起来，求出原问题的解。

与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的 子子问题。这种情况下分治法会重复的求解那些公共的子子问题。而动态规划算法对每个子子问题只求解一次，将其存放在某一个表格中，无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作，特别是当问题规模比较大的时候，在时间上有显著的区别

动态规划用来求解最优化问题。这类问题可以有很多可行的解，每个解都有一个值，我们希望需找具有最优值（最大或最小）的解。当然可能同时存在多个最优解（同时最大，或同时最小），动态规划只要求找到其中一个就好了。

动态规划的定义:

  1. 刻画一个最优解的结构特征
  2. 递归的定义最优解的值
  3. 计算最优解的值, 采用自低线上的方法
  4. 利用计算出的信息构建一个最优解

切割钢条问题

在算法导论中有一个例子, 切割钢条最大获利的例子. 说给定一个数组int[] nums, 下标代表长度, 值代表该长度的价格. 求给定长度n的最大价格.
[1,5,8,9,10,17,17,20,24,30]

第一种解法 暴力解法

当n=1时, 最大获利p1 = 1; 只有一种切法. 就是不切割
当n=2时, 最大获利p2 = 5; 不切割 和 切成两个长度为1的 p2 = max(p2, p1+p1);
当n=3时, 最大获利p3 = 8; 不切割 和 切成 1 + 2或者2+1 p3 = max(p3, p1+p2, p2+p1, p1+p1+p1)
当n=4时, 最大获利p4 = 10; 不切割 和 切成 1+1+1+1 1+3 3+1 2+2 p4 = max(p4, p1+p3, p2+p2, p3+p1, p1+p1+p1+p1)

由此推导出pn= max(pn, p1+p(p-1), p2+p(n-2),…p(n-1)+p1) 由于无法预知那种最优. 就枚举各种切法. 取最大值. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 

    * 计算钢条最大利润, 自顶向下遍历
    *
    * @param nums 目标数组
    * @param n    长度
    * @return 最大利
    */
   public int (int[] nums, int n) {
       if (n == 0) {
           return 0;
       }
       int res = 0;
       for (int i = 1; i <= n; i++) {
           res = Math.max(res, nums[i] + memoizedCutRodAux(nums, n - i));
       }
       return res;

   }

这种解法, 也叫树形递归.

截屏2019-11-1413.36.16.png

这种解法 一颗树有2的n次方个节点, 2的n次方-1个叶子节点. n=4时意味着会调用了16次. 所以调用次数T(n) = 2的n次方.

使用动态规划方法求解最优化切割问题

朴素的递归方法之所以的效率低. 就是反复的计算相同的子问题. 例如n=4, f(1) 计算了4次 f(0) 是8次. 所以最想想到的优化方案就是. 子问题的结果记录下来. 当递归计算时. 发现已经计算了. 返回结果就可以了. 这是典型的时空权衡.

带备忘录的自顶向下法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
public void t(int[] nums, int n) {
       int[] cache = new int[n + 1];
       Arrays.fill(cache, -1);
       int i = memoizedCutRodAuxCache(nums, n, cache);
       System.out.println("i = " + i);
   }

   
    * 计算钢条最大利润, 自顶向下遍历 添加缓存, 避免重复计算
    *
    * @param nums  目标数组
    * @param n     长度
    * @param cache 缓存
    * @return 最大利润
    */
   public int memoizedCutRodAuxCache(int[] nums, int n, int[] cache) {
       if (cache[n] >= 0) {
           return cache[n];
       }
       if (n == 0) {
           return 0;
       }
       int res = 0;
       for (int i = 1; i <= n; i++) {
           res = Math.max(res, nums[i] + memoizedCutRodAuxCache(nums, n - i, cache));
       }
       cache[n] = res;
       return res;

   }

这种递归的方式叫带备忘录的, 因为他记住了之前计算出的结果.

自底向上法

另外一种自底向上法. 希望任何子问题的求解都依赖于更小子问题的解. 因而我们可以将子问题按照规模排序. 由小到大的顺序求解. 意思是说找到dp[4]的结果.依赖于dp[3]的结果. dp[3]依赖于dp[2]依次力推.
找到了公式. 就可以从dp[1]开始计算, 求出dp[n];

dp[1] = 1; dp[2] = max(dp[2], nums[1]+dp[1]); dp[3] = max(dp[2], nums[1]+dp[2], nums[2]+dp[1]); 依次类推下去. 得出dp[n] = max(dp[n], nums[1]+dp[n-1], nums[2]+dp[n-2]….);

这样就找到了dp[n]和dp[n-1]的关系.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 


   * 计算钢条最大利润, 自底部向上遍历
   * dp 1 = max(nums[1], nums[1]+dp[0])
   * dp2 = max (nums[2], nums[1]+dp[1])
   * dp3 = max(nums[3], nums[1]+dp[2], nums[2]+dp[1], nums[3]+dp[0])
   * dp4 = max(num[4], nums[1]+dp[3], mums[2]+dp[2], nums[3]+dp[1], nums[4]+dp[0])
   *
   * @param nums 目标数组
   * @param n    长度
   * @return 最大利润
   */
  public int memoizedCutRodAux1(int[] nums, int n) {
      if (n == 0) {
          return 0;
      }
      int[] dp = new int[n + 1];
      dp[0] = 0;

      for (int i = 1; i <= n; i++) {
          int res = 0;
          for (int j = 1; j <= i; j++) {
              res = Math.max(res, nums[j] + dp[i - j]);
          }
          dp[i] = res;
      }
      return dp[n];

  }

爬楼梯问题

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。求出一共有多少种走法。

暴力解法. 自顶向下

因为步长为1或者2, 那么很容易想到 f(n) = f(n-1) + f(n-2);
边界 f(0) = 0 f(1) = 1 f(2) = 2

1
2
3
4
5
6
7
8
9
10
11
12
 
public int climb(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climb(n - 1) + climb(n - 2);
    }

这个解法和切钢条的暴力解法一样都是树形的. 子问题会反复计算.

动态规划

自顶向下 带备忘录

将子问题的接保存起来. 避免重复计算. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 

private Map<Integer, Integer> cache = new HashMap<>();

    public int climbCache(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (cache.containsKey(n)) {
            System.out.println("n = " + n);
            return cache.get(n);
        }
        int i = climbCache(n - 1) + climbCache(n - 2);
        cache.put(n, i);
        return i;
    }
自底向上

这种解法要换个思路. 我们希望从最小的问题开始一级一级的网上求解. 关注点变成了子问题的解.
dp[0]=0; dp[1] = 1; dp[2]=2; dp[3]=dp[2]+dp[1];

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public int climbBottomUp(int n) {
       if (n <= 2) {
           return n;
       }
       int[] dp = new int[n + 1];
       dp[0] = 0;
       dp[1] = 1;
       dp[2] = 2;
       for (int i = 3; i <= n; i++) {
           dp[i] = dp[i - 1] + dp[i - 2];
       }
       return dp[n];
   }

工人金矿问题

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能