• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

DP动态规划(Python实现)

Alg admin 4年前 (2015-11-26) 11600次浏览 0个评论 扫描二维码

前言 _

我们遇到的问题中,有很大一部分可以用动态规划(简称 DP)来解。 解决这类问题可以很大地提升你的能力与技巧,我会试着帮助你理解如何使用 DP 来解题。 这篇文章是基于实例展开来讲的,因为干巴巴的理论实在不好理解。

注意:如果你对于其中某一节已经了解并且不想阅读它,没关系,直接跳过它即可。

简介(入门)

什么是动态规划,我们要如何描述它?

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度, 因此它比回溯法、暴力法等要快许多。

现在让我们通过一个例子来了解一下 DP 的基本原理。

首先,我们要找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。

“状态”代表什么及如何找到它?

“状态”用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚,跳过直接上例子。

如果我们有面值为 1 元、3 元和 5 元的硬币若干枚,如何用最少的硬币凑够 11 元? (表面上这道题可以用贪心算法,但贪心算法无法保证可以求出解,比如 1 元换成 2 元的时候)

首先我们思考一个问题,如何用最少的硬币凑够 i 元(i<11)?为什么要这么问呢? 两个原因:1.当我们遇到一个大问题时,总是习惯把问题的规模变小,这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的,除了规模变小,其它的都是一样的, 本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

好了,让我们从最小的 i 开始吧。当 i=0,即我们需要多少个硬币来凑够 0 元。 由于 1,3,5 都大于 0,即没有比 0 小的币值,因此凑够 0 元我们最少需要 0 个硬币。 (这个分析很傻是不是?别着急,这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够 0 元我们最少需要 0 个硬币。”会比较方便, 如果一直用纯文字来表述,不出一会儿你就会觉得很绕了。那么, 我们用 d(i)=j 来表示凑够 i 元最少需要 j 个硬币。于是我们已经得到了 d(0)=0, 表示凑够 0 元最小需要 0 个硬币。当 i=1 时,只有面值为 1 元的硬币可用, 因此我们拿起一个面值为 1 的硬币,接下来只需要凑够 0 元即可,而这个是已经知道答案的, 即 d(0)=0。所以,d(1)=d(1-1)+1=d(0)+1=0+1=1。当 i=2 时, 仍然只有面值为 1 的硬币可用,于是我拿起一个面值为 1 的硬币, 接下来我只需要再凑够 2-1=1 元即可(记得要用最小的硬币数量),而这个答案也已经知道了。 所以 d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里,你都可能会觉得,好无聊, 感觉像做小学生的题目似的。因为我们一直都只能操作面值为 1 的硬币!耐心点, 让我们看看 i=3 时的情况。当 i=3 时,我们能用的硬币就有两种了:1 元的和 3 元的( 5 元的仍然没用,因为你需要凑的数目是 3 元!5 元太多了亲)。 既然能用的硬币有两种,我就有两种方案。如果我拿了一个 1 元的硬币,我的目标就变为了: 凑够 3-1=2 元需要的最少硬币数量。即 d(3)=d(3-1)+1=d(2)+1=2+1=3。 这个方案说的是,我拿 3 个 1 元的硬币;第二种方案是我拿起一个 3 元的硬币, 我的目标就变成:凑够 3-3=0 元需要的最少硬币数量。即 d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是,我拿 1 个 3 元的硬币。好了,这两种方案哪种更优呢? 记得我们可是要用最少的硬币数量来凑够 3 元的。所以, 选择 d(3)=1,怎么来的呢?具体是这样得到的:d(3)=min{d(3-1)+1, d(3-3)+1}。

OK,码了这么多字讲具体的东西,让我们来点抽象的。从以上的文字中, 我们要抽出动态规划里非常重要的两个概念:状态和状态转移方程。

上文中 d(i)表示凑够 i 元需要的最少硬币数量,我们将它定义为该问题的”状态”, 这个状态是怎么找出来的呢?我在另一篇文章动态规划之背包问题(一)中写过: 根据子问题定义状态。你找到子问题,状态也就浮出水面了。 最终我们要求解的问题,可以用这个状态来表示:d(11),即凑够 11 元最少需要多少个硬币。 那状态转移方程是什么呢?既然我们用 d(i)表示状态,那么状态转移方程自然包含 d(i), 上文中包含状态 d(i)的方程是:d(3)=min{d(3-1)+1, d(3-3)+1}。没错, 它就是状态转移方程,描述状态之间是如何转移的。当然,我们要对它抽象一下,

d(i)=min{ d(i-vj)+1 },其中 i-vj >=0,vj表示第 j 个硬币的面值;

有了状态和状态转移方程,这个问题基本上也就解决了。当然了,Talk is cheap,show me the code!

伪代码如下:


Python 代码如下:

import os

Min=[x for x in range(12)];
VN=[1,3,5];
for i in range(1,12,1):
    for j in range(3):
        if VN[j]<=i and Min[i-VN[j]]+1<Min[i]:
            Min[i]=Min[i-VN[j]]+1;

print(Min[1::1]);

下图是当 i 从 0 到 11 时的解:

从上图可以得出,要凑够 11 元至少需要 3 枚硬币。

此外,通过追踪我们是如何从前一个状态值得到当前状态值的, 可以找到每一次我们用的是什么面值的硬币。比如,从上面的图我们可以看出, 最终结果 d(11)=d(10)+1(面值为 1),而 d(10)=d(5)+1(面值为 5),最后 d(5)=d(0)+1 (面值为 5)。所以我们凑够 11 元最少需要的 3 枚硬币是:1 元、5 元、5 元。

注意:原文中这里本来还有一段的,但我反反复复读了几遍, 大概的意思我已经在上文从 i=0 到 i=3 的分析中有所体现了。作者本来想讲的通俗一些, 结果没写好,反而更不好懂,所以这段不翻译了。

初级

上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题, 如何找到状态之间的转移方式(即找到状态转移方程)。 为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程)

OK,上例子,看看它是如何工作的。

一个序列有 N 个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。 (讲 DP 基本都会讲到的一个问题 LIS:longest increasing subsequence)

正如上面我们讲的,面对这样一个问题,我们首先要定义一个“状态”来代表它的子问题, 并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关, 而独立于后面的状态。

让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。 假如我们考虑求 A[1],A[2],…,A[i]的最长非降子序列的长度,其中 i<N, 那么上面的问题变成了原问题的一个子问题(问题规模变小了,你可以让 i=1,2,3 等来分析) 然后我们定义 d(i),表示前 i 个数中以 A[i]结尾的最长非降子序列的长度。OK, 对照“入门”中的简单题,你应该可以估计到这个 d(i)就是我们要找的状态。 如果我们把 d(1)到 d(N)都计算出来,那么最终我们要找的答案就是这里面最大的那个。 状态找到了,下一步找出状态转移方程。

为了方便理解我们是如何找到状态转移方程的,我先把下面的例子提到前面来讲。 如果我们要求的这 N 个数的序列是:

5,3,4,8,6,7

根据上面找到的状态,我们可以得到:(下文的最长非降子序列都用 LIS 表示)

  • 前 1 个数的 LIS 长度 d(1)=1(序列:5)
  • 前 2 个数的 LIS 长度 d(2)=1(序列:3;3 前面没有比 3 小的)
  • 前 3 个数的 LIS 长度 d(3)=2(序列:3,4;4 前面有个比它小的 3,所以 d(3)=d(2)+1)
  • 前 4 个数的 LIS 长度 d(4)=3(序列:3,4,8;8 前面比它小的有 3 个数,所以 d(4)=max{d(1),d(2),d(3)}+1=3)

OK,分析到这,我觉得状态转移方程已经很明显了,如果我们已经求出了 d(1)到 d(i-1), 那么 d(i)可以用下面的状态转移方程得到:

d(i) = max{1, d(j)+1},其中 j<i,A[j]<=A[i]

用大白话解释就是,想要求 d(i),就把 i 前面的各个子序列中, 最后一个数不大于 A[i]的序列长度加 1,然后取出最大的长度即为 d(i)。 当然了,有可能 i 前面的各个子序列中最后一个数都大于 A[i],那么 d(i)=1, 即它自身成为一个长度为 1 的子序列。

分析完了,上图:(第二列表示前 i 个数中 LIS 的长度, 第三列表示,LIS 中到达当前这个数的上一个数的下标,根据这个可以求出 LIS 序列)

Talk is cheap, show me the code:

#include <iostream>
using namespace std;

int lis(int A[], int n){
    int *d = new int[n];
    int len = 1;
    for(int i=0; i<n; ++i){
        d[i] = 1;
        for(int j=0; j<i; ++j)
            if(A[j]<=A[i] && d[j]+1>d[i])
                d[i] = d[j] + 1;
        if(d[i]>len) len = d[i];
    }
    delete[] d;
    return len;
}
int main(){
    int A[] = {
        5, 3, 4, 8, 6, 7
    };
    cout<<lis(A, 6)<<endl;
    return 0;
}

Python 代码如下:

import sys

def lis(*args,num=1):
    d=[0]*num;
    len_num=1;
    for i in range(num):
        d[i]=1;
        for j in range(i):
            if args[j]<=args[i] and d[i]<d[j]+1:                 
                 d[i]=d[j]+1;             
            if d[i]>len_num:
                len_num=d[i];
    return len_num;

print(lis(5,3,4,8,6,7));
                
        

该算法的时间复杂度是 O(n2 ),并不是最优的解法。 还有一种很巧妙的算法可以将时间复杂度降到 O(nlogn),网上已经有各种文章介绍它, 这里就不再赘述。传送门: LIS 的 O(nlogn)解法。 此题还可以用“排序+LCS”来解,感兴趣的话可自行 Google。

练习题

无向图 G 有 N 个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点 1 到结点 N 的最短路径,或者输出不存在这样的路径。

提示:在每一步中,对于那些没有计算过的结点, 及那些已经计算出从结点 1 到它的最短路径的结点,如果它们间有边, 则计算从结点 1 到未计算结点的最短路径。

尝试解决以下来自 topcoder 竞赛的问题:

转载自:http://www.hawstein.com/posts/dp-novice-to-advanced.html


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明DP 动态规划(Python 实现)
喜欢 (22)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!