Dynamic Programming

Introduction

Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly ‘Remember your Past’) . If the given problem can be broken up into smaller sub-problems and these smaller sub-problems can be in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping sub-problems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem.

major points

  • can be divided into smaller sub-problems
  • there are strong over-lapping among sub-problems

typical methods

There are two ways of doing this.

  1. Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already (different from the pre-defined value), then just return the saved answer. If it has not been solved, solve it and save the answer. This is referred to as Memoization.
  2. Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial sub-problems, up towards the given problem. In this process, it is guaranteed that the sub-problems are solved before solving the problem. This is referred to as Dynamic Programming.

difference with divide and conquer

Note that divide and conquer is slightly a different technique. In that, we divide the problem in to non-overlapping sub-problems and solve them independently, like in merge sort and quick sort.

friendship with greedy

Complementary to Dynamic Programming are Greedy Algorithms which make a decision once and for all every time they need to make a choice, in such a way that it leads to a near-optimal solution. A Dynamic Programming solution is based on the principal of Mathematical Induction greedy algorithms require other kinds of proof.

Examples


Even some of the high-rated coders go wrong in tricky DP problems many times. DP gurus suggest that DP is an art and its all about Practice. The more DP problems you solve, the easier it gets to relate a new problem to the one you solved already and tune your thinking very fast. It looks like a magic when you see some one solving a tricky DP so easily.

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maximalSquare(vector<vector<char>>& matrix)
{
int rowSize = matrix.size();
if(!rowSize) return 0;
int colSize = matrix[0].size();
if(!colSize) return 0;
int square[rowSize+1][colSize+1];
memset(square, 0, sizeof(int)*(rowSize+1)*(colSize+1));
int maxWidth = 0;
for(int r = 1; r <= rowSize; ++r)
{
for(int c = 1; c <= colSize; ++c)
{
if(matrix[r-1][c-1] == '1')
square[r][c] = min(min(square[r-1][c], square[r][c-1]), square[r-1][c-1]) + 1;
maxWidth = max(maxWidth, square[r][c]);
}
}
return maxWidth*maxWidth;
}

House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int rob(vector<int>& nums)
{
int size = nums.size();
if(size == 0) return 0;
if(size == 1) return nums[0];
if(size == 2) return max(nums[0], nums[1]);
int pre = nums[0], cur = max(nums[0], nums[1]); //the maximum can be robbed till now
int t = 0, withFirst = 0;
for(int i = 2; i < size-1; ++i)
{
t = pre;
cur = max(pre=cur, t+nums[i]);
}
withFirst = cur;
pre = nums[1], cur = max(nums[1], nums[2]);
for(int i = 3; i < size; ++i)
{
t = pre;
cur = max(pre=cur, t+nums[i]);
}
return max(withFirst, cur);
}

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProduct(vector<int>& nums)
{
int lProduct = 1, rProduct = 1;
int size = nums.size(), maxProduct = nums[0];
for(int i = 0; i < size; ++i)
{
lProduct *= nums[i];
rProduct *= nums[size-i-1];
maxProduct = max(maxProduct, max(lProduct, rProduct));
if(lProduct == 0) lProduct = 1;
if(rProduct == 0) rProduct = 1;
}
return maxProduct;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProduct(vector<int>& nums)
{
int size = nums.size();
int minProduct = nums[0], maxProduct = nums[0], ret = nums[0];
for(int i = 1; i < size; ++i)
{
if(nums[i] < 0) swap(minProduct, maxProduct);
maxProduct = max(maxProduct*nums[i], nums[i]);
minProduct = min(minProduct*nums[i], nums[i]);
ret = max(ret, maxProduct);
}
return ret;
}

Classic


Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

Typical DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLIS(vector<int>& nums)
{
int size = nums.size();
if(!size) return 0;
int subLens[size];
subLens[0] = 1;
int maxLen = 1;
for(int i = 1; i < size; ++i)
{
subLens[i] = 1;
for(int j = i-1; j >= 0; --j)
{
if(nums[i] > nums[j])
subLens[i] = max(subLens[i], subLens[j]+1);
maxLen = max(maxLen, subLens[i]);
}
}
return maxLen;
}

But actually we can do much better using window in which if we manually implement the lower_bound via binary search we can achieve further better.

1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLIS(vector<int>& nums)
{
int top = -1, size = nums.size();
if(size == 0) return 0;
vector<int> window;
for(int i = 0; i < size; ++i)
{
auto iter = lower_bound(window.begin(), window.end(), nums[i]);
if(iter == window.end()) window.push_back(nums[i]);
else *iter = nums[i];
}
return window.size();
}

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minPathSum(vector<vector<int>>& grid)
{
int rowSize = grid.size();
if(rowSize == 0) return 0;
int colSize = grid[0].size();
int cur[colSize]{0};
partial_sum(grid[0].begin(), grid[0].end(), cur); //column-based
for(int r = 1; r < rowSize; ++r)
{
cur[0] += grid[r][0];
for(int c = 1; c < colSize; ++c)
cur[c] = min(cur[c], cur[c-1])+grid[r][c];
}
return cur[colSize-1];
}

Longest Common Subsequence (LCS)

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Here is an example:
S = “rabbbit”, T = “rabbit”
Return 3.

1
2
3
4
5
6
7
8
9
10
int numDistinct(string s, string t)
{
int sLen = s.length(), tLen = t.length();
int cur[tLen+1]{0};
cur[0] = 1;
for(int i = 1; i <= sLen; ++i)
for(int j = tLen; j > 0; --j)
if(t[j-1] == s[i-1]) cur[j] += cur[j-1];
return cur[tLen];
}

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”, s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isInterleave(string s1, string s2, string s3)
{
int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
if(len1+len2 != len3) return false;
if(len3 == 0) return true;
int cur[len2+1]{0}; //each length of s2
cur[0] = 1;
for(int i = 1; i<=len2 && s2[i-1]==s3[i-1]; ++i) cur[i] = 1;
for(int i = 1; i <= len1; ++i)
{
for(int j = 0; j <= len2; ++j)
{
cur[j] = (j>0 && cur[j-1] && s2[j-1]==s3[i+j-1]) //s2 will take the position
|| (cur[j] && s1[i-1]==s3[i+j-1]); //s1 takes the position
}
}
return cur[len2];
}

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minDistance(string word1, string word2)
{
int len1 = word1.length(), len2 = word2.length(), pre = 0;
int steps[len2+1]{0};
for(int i = 0; i <= len2; ++i) steps[i] = i;
for(int i = 1; i <= len1; ++i)
{
pre = i-1; //used as [i-1][j-1]
steps[0] = i;
for(int j = 1; j <= len2; ++j)
{
int t = steps[j];
if(word1[i-1] == word2[j-1]) steps[j] = pre;
else steps[j] = min(steps[j-1], min(steps[j], pre))+1; //insert, delete and replace
pre = t;
}
}
return steps[len2];
}

Wildcard Matching

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

  • ‘?’ Matches any single character.
  • ‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, ““) → true
isMatch(“aa”, “a
“) → true
isMatch(“ab”, “?“) → true
isMatch(“aab”, “c
a*b”) → false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isMatch(string s, string p)
{
int sLen = s.length(), pLen = p.length();
int match[sLen+1]{false};
match[0] = true;
for(int i = 1; i <= pLen; ++i)
{
if(p[i-1] == '*')
{
for(int j = 1; j <= sLen; ++j)
match[j] = match[j] || match[j-1]; //match zero, one or more
}
else
{
for(int j = sLen; j > 0; --j)
match[j] = match[j-1] && (p[i-1]=='?' || p[i-1]==s[j-1]);
match[0] = false; //once there is a non-asterisk
}
}
return match[sLen];
}

Sometimes there are just funny solutions to complicated problems as follows, quite intuitive and efficient.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isMatch(string s, string p)
{
int i = 0, j = 0;
int sA = -1, pA = -1;
int sLen = s.length(), pLen = p.length();
while(i < sLen)
{
if(s[i]==p[j] || p[j]=='?') { i++, j++; continue; }
if(p[j] == '*') { pA = j++; sA = i; continue; } //match zero
if(pA > -1) { j = pA+1; i = ++sA; continue; } //match one or more
return false;
}
while(p[j] == '*') j++;
return j == pLen;
}

Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘*’.

  • ‘.’ Matches any single character.
  • ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.
“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “c
a*b”) → true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isMatch(string s, string p)
{
int sLen = s.length(), pLen = p.length();
int match[pLen+1][sLen+1];
memset(match, 0, sizeof(int)*(pLen+1)*(sLen+1));
match[0][0] = 1;
for(int i = 2; i <= pLen; i += 2)
if(p[i-1] == '*') match[i][0] = 1; else break;
for(int i = 1; i <= pLen; ++i)
{
if(p[i-1] == '*')
for(int j = 1; j <= sLen; ++j) //match zero, one or more
match[i][j] = match[i-2][j] || ((p[i-2]=='.' || p[i-2]==s[j-1]) && match[i][j-1]);
else
for(int j = 1; j <= sLen; ++j)
match[i][j] = match[i-1][j-1] && (p[i-1]=='.' || p[i-1]==s[j-1]);
}
return match[pLen][sLen];
}

A simple DFS solution can be quite efficient in this case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
private:
bool isMatch(char* s, char* p)
{
if(*p == '\0') return *s == '\0';
if(*(p+1) == '*')
return isMatch(s, p+2) || (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, p));
else
return (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, ++p));
}
public:
bool isMatch(string s, string p)
{
return isMatch((char*)s.c_str(), (char*)p.c_str());
}
};

Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int longestValidParentheses(string s)
{
if(s.empty()) return 0;
int len = s.length(), longest = 0;
int maxSub[len] = {0};
for(int i = 0; i < len; ++i)
{
if(s[i] == ')')
{
int t = i-maxSub[i-1];
if(t>0 && s[t-1] == '(') maxSub[i] = (t>1? maxSub[t-2] : 0)+maxSub[i-1]+2;
longest = max(longest, maxSub[i]);
}
}
return longest;
}

Integrated problems


These problems are not just about DP any more, they will cover greedy, backtracking, math and sometimes even some original tricks. Have fun here…

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

Using DP to accelerate the backtracking - typical integrated problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private:
int sLen;
void search(string&s, int pos, bool** isPal, vector<string>& v, vector<vector<string>>& vv)
{
if(pos == sLen) { vv.push_back(v); return ; }
for(int i = pos; i < sLen; ++i)
{
if(isPal[pos][i])
{
v.push_back(s.substr(pos, i-pos+1));
search(s, i+1, isPal, v, vv);
v.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s)
{
sLen = s.length();
bool **isPal = (bool**)malloc(sizeof(bool*)*sLen);
for(int i = 0; i < sLen; ++i)
{
isPal[i] = (bool*)malloc(sizeof(bool)*sLen);
memset(isPal[i], 0, sizeof(bool)*sLen);
}
for(int i = sLen-1; i >= 0; --i)
{
for(int j = i; j < sLen; ++j)
{
if(s[j]==s[i] && (j-i<2 || isPal[i+1][j-1]))
isPal[i][j] = true;
}
}
vector<string> v;
vector<vector<string>> vv;
search(s, 0, isPal, v, vv);
return vv;
}
};

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. 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”].

Using DP to accelerate the backtracking - typical integrated problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
private:
int sLen, wMinLen, wMaxLen;
void search(string& s, int pos, bool isBreakable[], string path, vector<string>& v, unordered_set<string>& wordDict)
{
for(int len = wMinLen; len <= min(wMaxLen, sLen-pos); ++len)
{
string t = s.substr(pos, len);
if(isBreakable[pos+len] && wordDict.count(t))
{
if(pos+len == sLen) v.push_back(path+t);
else search(s, pos+len, isBreakable, path+t+" ", v, wordDict);
}
}
}
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict)
{
sLen = s.length();
wMinLen = INT_MAX, wMaxLen = INT_MIN;
for(auto& w: wordDict) //accelerating factor
{
wMinLen = min(wMinLen, (int)w.length());
wMaxLen = max(wMaxLen, (int)w.length());
}
bool isBreakable[sLen+1]{false}; //acclerating factor
isBreakable[sLen] = true;
for(int i = sLen-wMinLen; i >= 0; --i)
{
for(int len = wMinLen; len <= min(wMaxLen, sLen-i); ++len)
{
string t = s.substr(i, len);
if(isBreakable[i+len] && wordDict.count(t))
isBreakable[i] = true;
}
}
vector<string> v;
search(s, 0, isBreakable, "", v, wordDict);
return v;
}
};

Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8] Return 167
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxCoins(vector<int>& nums)
{
nums.insert(nums.begin(), 1);
nums.insert(nums.end(), 1);
int size = nums.size();
int dp[size][size];
memset(dp, 0, sizeof(int)*size*size);
for(int d = 2; d < size; ++d)
{
for(int l = 0; l+d <size; ++l)
{
int r = l+d;
for(int j = l+1; j < r; ++j) //j here is the last to burst
dp[l][r] = max(dp[l][r], dp[l][j]+dp[j][r]+nums[l]*nums[j]*nums[r]);
}
}
return dp[0][size-1];
}

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = “great”:
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that “rgeat” is a scrambled string of “great”.
Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that “rgtae” is a scrambled string of “great”.
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Quite typical DP solution but we have to transferring this problem into proper forms first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isScramble(string s1, string s2)
{
int len = s1.length(), i = 0, j = 0, k = 0;
if(!len) return true;
int match[len+1][len][len]{{{0}}};
for(i = 0; i < len; ++i)
for(j = 0; j < len; ++j)
match[1][i][j] = (s1[i]==s2[j]);
for(int size = 2; size <= len; ++size)
for(i = 0; i <= len-size; ++i)
for(j = 0; j <= len-size; ++j)
for(k = 1; k<size&&!match[size][i][j]; ++k)
match[size][i][j] = (match[k][i][j]&&match[size-k][i+k][j+k]) ||
(match[k][i+size-k][j]&&match[size-k][i][j+k]);
return match[len][0][0];
}

Another backtracking solution considering symmetric features of the scrambled string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
int count[256];
bool isnScramble(const char* s1, const char* s2, int len)
{
if(!strncmp(s1, s2, len)) return true;
memset(count, 0, sizeof(int)*256);
for(int i = 0; i < len; ++i) count[s1[i]]++, count[s2[i]]--;
for(int i = 0; i < 256; ++i) if(count[i]) return false;
for(int i = 1; i < len; ++i)
if((isnScramble(s1, s2, i)&&isnScramble(s1+i, s2+i, len-i)) ||
(isnScramble(s1+len-i, s2, i)&&isnScramble(s1, s2+i, len-i))) return true;
return false;
}
public:
bool isScramble(string s1, string s2)
{
return isnScramble(s1.c_str(), s2.c_str(), s1.length());
}
};

Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine.
Example 1: nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2: nums: [1,2,4,8]
Result: [1,2,4,8]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> largestDivisibleSubset(vector<int>& nums)
{
int size = nums.size();
if(!size) return vector<int>();
sort(nums.begin(), nums.end()); //essential
//the maximal amount till current index and its corresponding last divisible index;
vector<pair<int, int>> maxWithIndex(1, make_pair(1, -1));
int globalMax = 1, index = 0;
for(int i = 1; i < size; ++i)
{
int maxCount = 1, preIndex = -1;
for(int j = i-1; j >=0; --j)
{
if(nums[i]%nums[j]==0 && maxWithIndex[j].first>=maxCount)
maxCount = maxWithIndex[j].first+1, preIndex = j;
}
maxWithIndex.emplace_back(maxCount, preIndex);
if(maxCount > globalMax) globalMax = maxCount, index = i; //maintain the global max
}
vector<int> v;
for(int i = 0; i < globalMax; ++i, index = maxWithIndex[index].second) //ensure ascending order
v.insert(v.begin(), nums[index]);
return v;
}

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Typical DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numSquares(int n)
{
static int mins[100000]{0}; //quite limites solution here
static int i = 1;
if(mins[n]) return mins[n];
for(; i <= n; ++i)
{
int localMin = i;
for(int j = sqrt(i); j > 0; --j)
localMin = min(localMin, mins[i-j*j]+1);
mins[i] = localMin;
}
return mins[n];
}

But actually there is a math solution which can be pretty simple and clean as Lagrange’s four-square theorem whose formula will be 4^k(8m+7) if there are four squares to make up the number.

1
2
3
4
5
6
7
8
9
10
11
int numSquares(int n)
{
while(!(n&3)) n /= 4;
if(n%8 == 7) return 4;
for(int a = sqrt(n); a > 0; --a)
{
int b = sqrt(n-a*a);
if(a*a+b*b == n) return !b? 1 : 2;
}
return 3;
}

Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution
{
public:
//select the maximal number in certain length within one vector;
vector<int> maxVector(vector<int> nums, int k)
{
while (nums.size() > k)
{
int i = 0, n = nums.size();
for (; i < n - 1; ++i) //at least erase one element each time;
{
if (nums[i] < nums[i + 1])
{
nums.erase(nums.begin() + i);
break;
}
}
if (i == n - 1) nums.erase(nums.begin() + i);
}
return nums;
}
//compare two vectors from certain index adopting lexical order;
//if the first vector is bigger return true otherwise return false;
bool compare(vector<int> &nums1, int i, vector<int> &nums2, int j)
{
while (i<nums1.size() && j<nums2.size() && nums1[i]==nums2[j]) ++i, ++j;
if (i<nums1.size() && j<nums2.size()) return nums1[i]>nums2[j];
else if(j == nums2.size()) return true;
else return false;
}
//get the first k numbers which form the largest lexical sequence;
vector<int> merge(vector<int> &nums1, vector<int> &nums2, int k)
{
vector<int> res(k, 0);
for (int i=0, j=0, r=0; r < k; ++r)
res[r] = compare(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
return res;
}
//AC - the most intuitive solution;
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
int len1=nums1.size(), len2=nums2.size();
vector<int> v(k, 0), v1, v2, t;
for (int l1 = max(0, k-len2); l1 <= min(k, len1); ++l1)
{
v1 = maxVector(nums1, l1);
v2 = maxVector(nums2, k-l1);
t = merge(v1, v2, k);
if (compare(t, 0, v, 0)) v = t;
}
return v;
}
};

This solution can be further optimized…

Always welcome new ideas and practical tricks, just leave them in the comments!