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