32 {
33 if (size <= 0 || max_step < min_step || min_step >= size) {
34 return nullptr;
35 }
37 if (debug) {
38 tprintf(
"min = %d, max=%d\n", min_step, max_step);
39 }
40
41 for (int i = 0; i < size; ++i) {
42 for (int offset = min_step; offset <= max_step; ++offset) {
43 DPPoint *prev = offset <= i ? points + i - offset :
nullptr;
44 int64_t new_cost = (points[i].*cost_func)(prev);
45 if (points[i].best_prev_ != nullptr && offset > min_step * 2 &&
46 new_cost > points[i].total_cost_) {
47 break;
48 }
49 }
50 points[i].total_cost_ += points[i].local_cost_;
51 if (debug) {
52 tprintf(
"At point %d, local cost=%d, total_cost=%d, steps=%d\n", i, points[i].local_cost_,
53 points[i].total_cost_, points[i].total_steps_);
54 }
55 }
56
57 int best_cost = points[size - 1].total_cost_;
58 int best_end = size - 1;
59 for (int end = best_end - 1; end >= size - min_step; --end) {
60 int cost = points[end].total_cost_;
61 if (cost < best_cost) {
62 best_cost = cost;
63 best_end = end;
64 }
65 }
66 return points + best_end;
67}
void tprintf(const char *format,...)