[ACE] Dynamic Programming

Overview

There are various general methods for finding solutions to problems.
Common ones include:
  • Brute force - “generate and test”
  • Divide and conquer
  • Heuristics
  • Dynamic Programming

Brute Force

This is roughly “generate and test”, generate all potential solutions and test for which ones are actual solutions.
This method is extremely inefficient, as is O(n!), but can be useful in some small cases.

Divide and Conquer

Recursively, break the problem into smaller pieces, solve them, and put them back together.
Merge-sort and Quick-sort were classic examples of this.

Heuristics

Two common types:
  • Decisions within a procedure that gives optimal answer to make it go faster.
  • Decisions within a procedure that might not give optimal answers, but are designed to give good answers that are impractical to obtain otherwise.
    Examples:
  • “Admissible heuristic” in A* search - decreases the search time compared to plain search
  • “pick a random pivot” in quick sort

Greedy algorithms

  • A common “heuristic” is to be greedy
  • Take the decision that looks best in short term
  • Prim’s algorithm for constructing a Minimal Spanning Tree is a greedy algorithm: it just adds the shortest edge without worrying about the overall structure, without looking ahead. It makes a locally optimal choice at each step.
  • Sometimes greedy algorithms can still give optimal answers
  • Sometimes greedy algorithms cannot guarantee to give optimal answers, example is “Change-Giving”
  • enter image description here

“Min-Coins-Change-Giving”

“Obviously” this can be solved by enumerating all possible subsets of S, selecting those that sum to K, and picking a subset with the fewest elements.
  • But with n coins there are 2^n subsets and so this “generate-and-test” naive algorithm is exponential in the worst case.
  • Can we do better? Firstly, consider greedy strategies:
  • Greedy strategy: start with the largest coin which is available; for the remaining change, again pick the largest coin; and so on.
  • Coins = {50, 50, 20 ,20, 20, 2, 2, 2 ,2, 2} Change = 60
  • Greedy method picks {50, 2, 2, 2, 2, 2} - 6coins
  • But can do it with {20, 20, 20} - 3 coins
    That’s why we need DP!

Dynamic Programming(DP)

DP is a general method that can be suitable when the optimal solutions satisfy a “decomposition property”:
  • Splitting an optimal solution into sub-solutions
  • So optimal solutions can be built out of optimal solutions of (smaller) sub-problems
  • So solve small sub-problems first and build up towards the full solution

Subset-Sum

Given multi-set S of positive integers x[i] and a target K:
Is there a subset of S that sums to exactly k?
The simple underlying idea is to suppose we have found all the best answers for the coins x[0],…x[i-1] and then want to also add the effect of one more coin x[i]:
  • if some subset summed to m, then with the inclusion x[i] we can also find a subset that sums to m+x[i]
  • and with one more coin than was recorded as possible for m
  • If a set of coins had already been found then take the one that gives the minimum.

Complexity

  • Outer loop has to consider all the coins –O(n)
  • Inner loop scans the entire array Y – hence O(k)
  • Overall is O(n K), much better than O(2^n)

Is this all? No!

In some ACM competition and OJ like LeetCode, there are a lot of question related to DP.

Coins change 2


My answer:





House robber



This is also a easy DP problem.
Think that:
  • On every house the robber robbed, the benefit is either: the benefit of this house + the benefit of the second previous house or the benefit of previous house(if the robber doesn’t rob this house)
  • There is a DP equation: DP[i] = max(DP[i-1], DP[i-2] + nums[i]);

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文