Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
学位和证书

浏览 Coursera 的全部课程

浏览
搜索
企业版
登录
免费加入

Reconstructing a Solution

Loading...

Algorithmic Toolbox

加州大学圣地亚哥分校

4.7（4,591 个评分） | 150K 名学生已注册

课程 1（共 6 门，数据结构与算法专项课程）

查看授课大纲

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

您将学习的技能

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

审阅

4.7（4,591 个评分）

5 stars
3,426 ratings
4 stars
929 ratings
3 stars
163 ratings
2 stars
34 ratings
1 star
39 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

从本节课中

Dynamic Programming 2

In this module, we continue practicing implementing dynamic programming solutions.

Problem Overview7:01

Subproblems6:57

Reconstructing a Solution8:56

教学方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

In this last video of this lesson, we show a method of reconstructing an actual

solution from two tables computed by our dynamic programming algorithm.

Okay, here on this slide we see two tables, m and capital M.

Computed by our dynamic program and

algorithm which contain minimal and maximal values respectively for

all possible subexpressions of our initial expression.

Let me first put in this for

all the rows and columns of these two matrices,

as well as numbers for our initial digits.

Well, in particular, we see by reading the contents of this cell

capital M of (1,6) that the maximal value of our initial expression is equal to 200,

and our goal is to unwind the whole solution, I mean,

parenthesizing of the initial expression, from these two tables.

So our first goal on this way is to understand from which two

subexpressions of the initial expression the value 200 was computed.

Well, let's see, when computing the value for the maximal value for

subexpression (1,6), we tried all possible splittings

of the expression (1,6) into two subexpressions.

Well, let's just go through all of them.

The first possibility is to split it into two subexpressions (1,1),

which corresponds just to the first digit which

is just 5, and subexpression (2,6),

with a minus sign between them, right.

So for both these two subexpressions we already know minimal values and

maximal values.

Well, let me mark them.

So this is the minimal value for the subexpression (1,1).

This is the maximal value for subexpression (1,1).

For (2,6), this is the minimal value,

-195, and this is a maximal value, 75.

So we would like to maximize this subexpression

one minus subexpression two, which means that we would like the first subexpression

to be as large as possible and the second subexpression to be as small as possible.

Well, this means that we need to

try to take the maximal value of the first subexpression which is five and

the minimal value of the second subexpression which is -195.

Well, we see that in this case,

5 minus -195 is the same as 5 plus 195,

which equals exactly 200, right,

which allows us to conclude, actually,

that the value 200 can be obtained as follows.

So, we subtract the minimum value which is -195

over the second subexpression from 5, right.

So we restored the last operation in an optimal

parenthesizing of the initial expression.

However, we still need to find out how to obtain

-195 out of the second subexpression.

Well, let's do this.

Okay, so we need to find how the minimum value

of the subexpression (2,6) was obtained.

Well, there are several possible splittings, once again,

of the subexpression (2,6) into two smaller sub-subexpressions.

The first of them is to split (2,6) into (2,2),

which just corresponds to the digit 8 plus (3,6).

Well, in this case, we would like the value to be as small as possible and

our sign is plus in this case, which means that we would like the value of

subexpression (2,2) to be as small as possible and

the value of subexpression (3,6) also to be as small as possible.

And you already know these values, they are in our tables,

so the minimal value of subexpression (2,2) is 8,

while the minimum value of subexpression (3, 6) is minus 91, right.

So we see that the sum of these two values is not equal to -195,

right, which means that plus is not the last operation

in the optimal parenthesizing that gives the minimum

value of subexpression (2, 6), right.

So let's check the next one.

Another possibility to split the subexpression (2, 6) is the following.

We split it into subexpression (2,

3) times subexpression (4, 6), right.

So once again, we would like to find the minimum value of subexpression (2, 6).

Well, let's see just all possibilities.

The minimum value of subexpression (2, 3) is 15.

It's maximal value is also 15.

As to subexpression (4,6), its minimum value is -13.

It's maximal value is 5.

And we would like the product of these two values to be as small as possible.

Well, it is not difficult to see that if we take just 15 and

multiply it, which is a minimum value of subexpression (2,3),

and multiply it by the minimum value of the subexpression (4,6),

which is -13, then we get exactly -195.

And this, in turn, allows us to get -195

from the subexpression (2,6).

We can do as follows.

We can first compute the sum of 8 and 7.

This gives us 15.

And then to multiply it by the result of the second subexpression.

Well, now it remains to find out how to get -13 out of this subexpression for

6, but in this small example, it is already easy to get -13.

Well, we just first compute the sum of 8 and 9 and

then subtract it from 4, right.

So this way we reconstructed the whole solution, I mean,

an optimal parenthesizing, or an optimal ordering, of our arithmetic operations,

leading to this value, to this maximal value, 200.

Let's just check it once again that our parenthesizing leads to the value 200,

indeed.

So we first compute the sum of 8 and 9.

This gives us 17.

We then subtract 17 from 4.

And this gives us -13.

We then compute the sum of 8 and 7.

This gives us 15.

We multiply 15 by -13.

It gives us -195, and, finally,

we subtract this number from 5, and we get 200, indeed.

So we reconstructed the whole solution.

In general, I mean for an expression consisting of n digits and

n minus 1 operations they can respond, an algorithm makes roughly quadratic number

of steps, because it needs to reconstruct n minus one operations, I mean,

an order of n minus one operations, going from last one to the first one.

And for each operation, it potentially needs to go through all possible

splittings into two subexpressions, and this number is at most M.

So the running time is bigger of ten times M, which is bigger of M squared.

And this technique is quite general.

It applies in many cases in the dynamic problem in algorithms.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司