动态规划学习笔记

June 5th, 2020

介绍

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 [1] 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

举例：

  • 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
  • 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
  • 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
  • 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等；

概念的意义

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

思想与性质

动态规划最重要的是掌握他的思想，动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。

实现套路

我们实现动态规划算法，常用的是2个实现套路，一个是自底向上，另外一个是自顶向下。无论是何种方式，我们都要明确动态规划的过程，把状态表示、状态转移、边界都考虑好。

问题

换硬币问题

想兑换100元钱，有1,2,5,10四种钱，问总共有多少兑换方法。

解: 推到过程,也可以用于写完代码将其当成测试用例。

  • f(0) = 1 设置一个初始值
  • f(1) = f(0)
  • f(2) = f(1) + f(0)
  • f(3) = f(2) + f(1)
  • ……
  • f(n) = f(n-1) + f(n-2) + f(n-5) + f(n-10)
  • f(n)，n >= 0

边界 n >= 0

状态表示 f(n)

状态转移方程 f(n) = f(n-1) + f(n-2) + f(n-5) + f(n-10)

转化成代码:

<?php

function coin($inputValue, $coins)
{
    $middle = [];
    $len = count($coins);
    $middle[0] = 1;

    for ($n = 1; $n <= $inputValue; $n++) {
        for ($i = 0; $i < $len; $i++) {
            if (empty($middle[$n])) {
                $middle[$n] = 0;
            }
            if ($n - $coins[$i] >= 0) {
                $middle[$n] += $middle[$n-$coins[$i]];
            }
        }
    }

    return $middle[$inputValue];
}

$coins = [1, 2, 5, 10];
$inputValue = 6;

echo coin($inputValue, $coins);

最大连续子数组和

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值，要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。

推到过程：

g(1) = g(0) + 1
f(1) = max(g(1), f(0)) = 1

g(2) = max(g(1) + (-2), 0) = 0
f(2) = max(g(2), f(1)) = 1

g(3) = max(g(2) + 3, 0) = 3
f(3) = max(g(3), f(2)) = 3

g(4) = max(g(3) + 10, 0) = 13
f(4) = max(g(4), f(3)) = 13

g(5) = max(g(4) + (-4), 0) = 9
f(5) = max(g(5), f(4)) = 13

g(6) = max(g(5) + 7, 0) = 16
f(6) = max(g(6), f(5)) = 16

g(7) = max(g(6) + 2, 0) = 18
f(7) = max(g(7), f(6)) = 18

g(8) = max(g(7) + (-5), 0) = 13
f(8) = max(g(8), f(7)) = 18

...

g(n) = max(g(n-1) + arr[n], 0)
f(n) = max(g(n), f(n-1))

边界：

n > 0

初始值定义:

g(0) = 0; f(0) = -0xFFFFFFFF;

状态表示 g(n) 表示累积到当前的和，和小于0，从下一个数字重新计算 f(n) 表示当前和最大值

状态转移方程 g(n) = max(g(n-1) + arr[n], 0) f(n) = max(g(n), f(n-1))

代码如下:

<?php

function maxSum($arr)
{
    $g = 0;
    $f = -0xFFFFFFFF;
    $l = count($arr);

    for ($i = 0; $i < $l; $i++) {
        if ($g <= 0) {
            $g = $arr[$i];
        } else {
            $g += $arr[$i];
        }

        if ($f < $g) {
            $f = $g;
        }
    }

    return $f;
}

echo maxSum([
    1, -2, 3, 10, -4, 7, 2, -5
]);

交替字符串

输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。

推到过程: s1字符索引用i表示,s2字符索引用j表示，s3字符索引用k表示。

i = 1, j = 0, k = 1;
i = 2, j = 0, k = 2;
i = 2, j = 1, k = 3;
i = 3, j = 1, k = 4;
i = 3, j = 2, k = 5;
i = 4, j = 2, k = 6;
i = 4, j = 3, k = 7;
<组成k的情况可能有两种，可能来自s1，也能可能来自于s2>
i = 4, j = 4, k = 8; i = 5, j = 3, k = 8;
i = 4, j = 5, k = 9;
i = 5, j = 5, k = 10;

由此可以知：k=i+j-1 进而用dp[i][j]表示状态,用一维数组无法表示两个状态，因为s3字符来源由s1或s2，所以是两种状态。

状态表示: dp[i][j] 代表s3[0...i+j-1]是否由s1[0..i-1]和s2[0...j-1]的字符组成

状态转移方程： dp[i][j] = ((s1[i-1] == s3[i+j-1]) && dp[i-1][j] || (s2[j-1] == s3[i+j-1]) && dp[i][j-1])

边界:

空串可以由空串组成

代码如下:

<?php

function alternate_str($s1, $s2, $s3)
{
    $l1 = strlen($s1);
    $l2 = strlen($s2);
    $l3 = strlen($s3);

    if ($l1 + $l2 !== $l3) {
        return false;
    }

    $dp = [];
    $dp[0][0] = true;

    for ($i = 0; $i <= $l1; $i++) {
        for ($j = 0; $j <= $l2; $j++) {
            if ($dp[$i][$j] ||
                ($i - 1 >= 0 && $dp[$i-1][$j] == true && $s1[$i-1] == $s3[$i+$j - 1]) ||
                ($j - 1 >= 0 && $dp[$i][$j-1] == true && $s2[$j-1] == $s3[$i+$j - 1])
            ) {
                $dp[$i][$j] = true;
            } else {
                $dp[$i][$j] = false;
            }
        }
    }
    echo json_encode($dp, 128);

    return $dp[$l1-1][$l2-1];
}

$s1 = 'aabcc';
$s2 = 'dbbca';
$s3 = 'aadbbcbcac';

echo alternate_str($s1, $s2, $s3);

参考

  • https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fr=aladdin
  • https://baijiahao.baidu.com/s?id=1631319141857419948&wfr=spider&for=pc
  • https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.05.md
  • https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.04.md

JY