Posts published in “Dynamic Programming”

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

Example 1:

1 2	Input: [1,3,5,4,7] Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

1 2	Input: [2,2,2,2,2] Output: 1

Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

Idea:

Dynamic Programming

Solution:

// Author: Huahua

class Solution {

public:

int findLengthOfLCIS(vector<int>& nums) {

if (nums.empty()) return 0;

int cur = 1;

int ans = 1;

for (int i = 1; i < nums.size(); ++i) {

if (nums[i] > nums[i-1]) {

++cur;

ans = max(ans, cur);

} else {

cur = 1;

}

return ans;

}

};

花花酱 LeetCode 63. Unique Paths II

By zxi on September 9, 2017

Problem:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

Idea:

Dynamic Programming

Solution:

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int n = obstacleGrid.size();

if (n == 0) return 0;

int m = obstacleGrid[0].size();

// f[i][j] = paths(i, j)

// INT_MIN -> not solved yet, solution unknown

f_ = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MIN));

return paths(m, n, obstacleGrid);

}

private:

vector<vector<int>> f_;

int paths(int x, int y, const vector<vector<int>>& o) {

// Out of bound, return 0.

if (x <= 0 || y <= 0) return 0;

// Reaching the starting point.

// Note, there might be an obstacle here as well.

if (x == 1 && y == 1) return 1 - o[0][0];

// Already solved, return the answer.

if (f_[y][x] != INT_MIN) return f_[y][x];

// There is an obstacle on current block, no path

if (o[y - 1][x - 1] == 1) {

f_[y][x] = 0;

} else {

// Recursively find paths.

f_[y][x] = paths(x - 1, y, o) + paths(x, y - 1, o);

}

// Return the memorized answer.

return f_[y][x];

}

};

Related Problems:

[解题报告] LeetCode 62. Unique Paths

花花酱 LeetCode 62. Unique Paths

By zxi on September 9, 2017

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Idea:

Dynamic Programming

Solution1:

C++

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

if (m < 0 || n < 0) return 0;

if (m == 1 && n == 1) return 1;

if (f_[m][n] > 0) return f_[m][n];

int left_paths = uniquePaths(m - 1, n);

int top_paths = uniquePaths(m, n - 1);

f_[m][n] = left_paths + top_paths;

return f_[m][n];

}

private:

unordered_map<int, unordered_map<int, int>> f_;

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

private int[][] dp;

private int m;

private int n;

public int uniquePaths(int m, int n) {

this.dp = new int[m][n];

this.m = m;

this.n = n;

return dfs(0, 0);

}

private int dfs(int x, int y) {

if (x > m - 1 || y > n - 1)

return 0;

if (x == m - 1 && y == n - 1)

return 1;

if (dp[x][y] == 0)

dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1);

return dp[x][y];

}

Solution2:

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

f[1][1] = 1;

for (int y = 1; y <= n; ++y)

for(int x = 1; x <= m; ++x) {

if (x == 1 && y == 1) {

continue;

} else {

f[y][x] = f[y-1][x] + f[y][x-1];

}

return f[n][m];

}

};

花花酱 LeetCode 241. Different Ways to Add Parentheses

By zxi on September 3, 2017

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1".

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms

C++

// Author: Huahua

namespace huahua {

int add(int a, int b) { return a+b; }

int minus(int a, int b) { return a-b; }

int multiply(int a, int b) { return a*b; }

} // namespace huahua

class Solution {

public:

vector<int> diffWaysToCompute(string input) {

return ways(input);

}

private:

const vector<int>& ways(const string& input) {

// Already solved, return the answer

if(m_.count(input)) return m_[input];

// Array for answer of input

vector<int> ans;

// Break the expression at every operator

for(int i=0;i<input.length();++i) {

char op = input[i];

// Split the input by an op

if(op=='+' || op=='-' || op=='*') {

const string left = input.substr(0, i);

const string right = input.substr(i+1);

// Get the solution of left/right sub-expressions

const vector<int>& l = ways(left);

const vector<int>& r = ways(right);

std::function<int(int,int)> f;

switch(op) {

case '+': f = huahua::add; break;

case '-': f = huahua::minus; break;

case '*': f = huahua::multiply; break;

}

// Combine the solution

for(int a : l)

for(int b : r)

ans.push_back(f(a,b));

}

// Single number, e.g. s = "3"

if(ans.empty())

ans.push_back(std::stoi(input));

// memorize the answer for input

m_[input].swap(ans);

return m_[input];

}

unordered_map<string, vector<int>> m_;

};

Python3

# Author: Huahua, 44 ms

class Solution:

def diffWaysToCompute(self, input):

ops = {'+': lambda x, y: x + y,

'-': lambda x, y: x - y,

'*': lambda x, y: x * y}

def ways(s):

ans = []

for i in range(len(s)):

if s[i] in "+-*":

ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]

if not ans: ans.append(int(s))

return ans

return ways(input)

花花酱 Leetcode 140. Word Break II

By zxi on September 2, 2017

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<string> wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

return wordBreak(s, dict);

}

private:

// >> append({"cats and", "cat sand"}, "dog");

// {"cats and dog", "cat sand dog"}

vector<string> append(const vector<string>& prefixes, const string& word) {

vector<string> results;

for(const auto& prefix : prefixes)

results.push_back(prefix + " " + word);

return results;

}

const vector<string>& wordBreak(string s, unordered_set<string>& dict) {

// Already in memory, return directly

if(mem_.count(s)) return mem_[s];

// Answer for s

vector<string> ans;

// s in dict, add it to the answer array

if(dict.count(s))

ans.push_back(s);

for(int j=1;j<s.length();++j) {

// Check whether right part is a word

const string& right = s.substr(j);

if (!dict.count(right)) continue;

// Get the ans for left part

const string& left = s.substr(0, j);

const vector<string> left_ans =

append(wordBreak(left, dict), right);

// Notice, can not use mem_ here,

// since we haven't got the ans for s yet.

ans.insert(ans.end(), left_ans.begin(), left_ans.end());

}

// memorize and return

mem_[s].swap(ans);

return mem_[s];

}

private:

unordered_map<string, vector<string>> mem_;

};

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def wordBreak(self, s, wordDict):

words = set(wordDict)

mem = {}

def wordBreak(s):

if s in mem: return mem[s]

ans = []

if s in words: ans.append(s)

for i in range(1, len(s)):

right = s[i:]

if right not in words: continue

ans += [w + " " + right for w in wordBreak(s[0:i])]

mem[s] = ans

return mem[s]

return wordBreak(s)