Dynamic Programming III
300. Longest Increasing Subsequence
If we define dp[i] as the longest increasing subsequence of [0, i]. Then dp[i] >= 1. And the state transition function is dp[i] = max(dp[i], dp[j] + 1) here j ∈ [0, i).
If we define dp[i] as the longest increasing subsequence of [0, i]. Then dp[i] >= 1. And the state transition function is dp[i] = max(dp[i], dp[j] + 1) here j ∈ [0, i).
a. Two pointers greedy solution.
Recently, I found a source code about Bluetooth positioning and navigation. Through its analysis and research, I have a deep understanding of the positioning and navigation process of the entire Bluetooth algorithm. Learn about Bluetooth signal acquisition, distance estimation, positioning calculation, Kalman model and other aspects.
This is also a full knapsack problem. It looks similar to the coins change ii, but the difference here is that we need to get the permutation of the solutions instead of combination. So in this case we need to iterate the knapsack space first, then iterate the items.
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Dynamic Programming (commonly referred to as DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and using the fact that the optimal solution to the overall problem depends upon the optimal solution to it’s individual subproblems. Here is an interesting Quora question How should I explain dynamic programming to a 4-year-old?.
Similar to other sgement related problems. The first thing we need to do is to sort the slice. Once we have a sorted segment slice, we can iterate over all items and merge them. Note there is one edge case we need to cover after the iteration, either we merged all segments into one or the last one can’t be merged into the previous segment.
To get a maximum sum, we need to convert as many negative numbers to positive ones. If there is still an odd times of converting number left, we just need to convert the smallest positive number to a negative one