Many algorithms or interview questions will be involved: dynamic programming problems. Dynamic programming, from a mathematical point of view, is that there is a set AAA with NNN elements. This set can construct the set class of 2n−12^n-12n−1 combinations:
The solution to the problem is to find a subset of SiSiSi that meets the conditions. On the other hand, we can traverse each subset of the set class and determine whether this subset meets the problem condition. If so, we can process the subset and finally get the optimal solution. The time complexity of this method is O(2n)O(2^n)O(2n), although it is not the best solution it is the most common solution for violence.
To achieve the general solution according to the above rules, you can follow the following steps (this article is implemented in OC language, other languages can refer to) :
1. Iterate over all subsets in the set class
Traversal of subsets can be achieved by recursive method, the code is as follows:
/** array: specifies the set to be processed. Start: specifies the initial location of the element. SubArray: saves the subset of the traversal. * /
void dynamicProgram(NSArray *array, NSInteger start, NSMutableArray *subArray) {
// Recursive calls generate subsets of set classes, respectively.
NSInteger count = array.count;
for (NSInteger i = start; i < count; i++) {
[subArray addObject:array[i]];
// subArray is a subset of the set class.
// make recursive calls
dynamicProgram(array, i + 1, subArray);
[subArray removeLastObject];
}
// An example of a method called is as follows:
dynamicProgram(@[@1The @2The @3The @4].0, [@[] mutableCopy]);
Copy the code2. Perform conditional judgment and processing for each subset
A generic method for traversing subsets is generated in the above code. To make the code more general, we can add a condition filter and a handler to let the caller do the custom processing, and a custom context information to hold the extension parameters to hold the results of each processing. So the code improvements above are as follows:
// Auxiliary functions.
static void dynamicProgramHelper(NSArray *array.void *ctx, NSInteger start, NSMutableArray *subArray, NSInteger * subIndexs, BOOL(^filter)(NSArray *subArray, NSInteger *subIndexs, void *ctx), BOOL(^handler)(NSArray *subArray, void* ctx) ) {
// Recursive calls generate subsets of set classes, respectively.
NSInteger count = array.count;
NSInteger subCount = subArray.count;
for (NSInteger i = start; i < count; i++) {
// Save the index of the subset elements in the collection.
subIndexs[subCount] = i;
[subArray addObject:array[i]];
if (filter(subArray, subIndexs, ctx)) {
if(! handler(subArray,ctx)) {break;
}
}
dynamicProgramHelper(array, ctx, i + 1, subArray, subIndexs, filter, handler); [subArray removeLastObject]; }}/** array: specifies the set to be processed. CTX: saves the context information. Filter: specifies the conditional filter. Return true if the condition is met to indicate that the computation will take place, false otherwise. Handler: Specifies the processor, with inputs such as subset and context. Return false to terminate processing if the best result has been achieved, otherwise return true to continue processing. * /
void dynamicProgram(NSArray *array.void *ctx, BOOL(^filter)(NSArray *subArray, NSInteger *subIndexs, void *ctx), BOOL(^handler)(NSArray *subArray, void *ctx) ) {
NSMutableArray *subArray = [NSMutableArray new];
NSInteger *subIndexs = malloc(sizeof(NSInteger)*array.count);
dynamicProgramHelper(array, ctx, 0, subArray, subIndexs, filter, handler);
free(subIndexs);
}
Copy the codeIn the general algorithm above, we decompose the processing of dynamic programming into conditions and calculations. Conditions are used to judge whether the requirements of computation are met, and calculations are performed on each subset that meets the conditions. So if we could divide everything into conditions and calculations then it would be easy to solve. Next we will use the above general dynamic programming algorithm to solve several classic problems:
1. Thief problem
Analysis of this problem can be seen: the condition is that houses can not be adjacent, that is, the index value can not differ 1. Calculation is finding the maximum amount of money. So the implementation code is as follows:
// Save the maximum amount as a context parameter.
NSInteger maxSum = 0;
dynamicProgram(@[@2The @7The @9The @3The @1], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
// If the houses are not contiguous, the subarray indexes are not contiguous.
// If two indexes differ by 1, the condition is not met.
NSInteger index = subIndexs[0];
for (NSInteger i = 1; i < subArray.count; i++) {
if (index == subIndexs[i] - 1) {
return NO;
}
index = subIndexs[i];
}
return YES;
}, ^BOOL(NSArray *subArray, void *ctx) {
// Calculate the sum of the current subset
NSInteger sum = 0;
for (NSNumber *num in subArray) {
sum += num.integerValue;
}
// Check whether it is the maximum. If not, change the maximum
NSInteger *pmaxSum = (NSInteger*)ctx;
if (sum > *pmaxSum) {
*pmaxSum = sum;
}
return YES;
});
NSLog(@"The largest amount stolen is :%ld",maxSum);
Copy the code2. Maximum subsequence sum
Analysis of this problem can be seen: the condition is that the positions must be adjacent, that is, the index values must differ by 1. Computation is finding the maximum value. You can see that this problem is the thief problem with the opposite condition, the same calculation. So the implementation code is as follows:
NSInteger maxSum = 0;
dynamicProgram(@[@2 -The @1The @- 3The @4The @- 1The @2The @1The @- 5The @4], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
// The positions must be adjacent, so the method of checking is that the indexes of the subarrays are adjacent.
// If there is no difference of 1 between the two indexes, the condition is not met.
NSInteger index = subIndexs[0];
for (NSInteger i = 1; i < subArray.count; i++) {
if(index ! = subIndexs[i] -1) {
return NO;
}
index = subIndexs[i];
}
return YES;
}, ^BOOL(NSArray *subArray, void *ctx) {
// Computes the sum of the current subset
NSInteger sum = 0;
for (NSNumber *num in subArray) {
sum += num.integerValue;
}
// Check whether it is the maximum. If not, change the maximum
NSInteger *pmaxSum = (NSInteger*)ctx;
if (sum > *pmaxSum) {
*pmaxSum = sum;
}
return YES;
});
NSLog(@"Sum of maximum subsequence :%ld",maxSum);
Copy the code3. Coin combination problem
So in this problem if the coins are of type 1,2,5, then the total is 11 dollars. So the array should be:,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,5,5 [1]. The condition becomes that the amount of money in the subset has to add up to 11. What we’re doing is we’re getting the smallest subset. So the code looks like this:
NSArray *coins = @[@1The @1The @1The @1The @1The @1The @1The @1The @1The @1The @1The @2The @2The @2The @2The @2The @5The @5];
// Start with the minimum number of sets.
NSMutableArray *minCoins = [coins mutableCopy];
dynamicProgram(coins, (__bridge void *)(minCoins), ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
// The condition is that the sum of elements must be equal to 11.
NSInteger sum = 0;
for (NSNumber *num in subArray) {
sum += num.integerValue;
}
return sum == 11;
}, ^BOOL(NSArray *subArray, void *ctx) {
// Select the smallest number.
NSMutableArray *minCoins = (__bridge NSMutableArray *)(ctx);
if (minCoins.count > subArray.count) {
[minCoins setArray:subArray];
}
return YES;
});
Copy the code