AOJ2305 Beautiful Currency

Beautiful Currency | Aizu Online Judge
DPが苦手すぎます。
　昇順に並んだ数列a(length : N)が与えられます。 a_i+1 mod a_i = 0がi(0 <= i < N - 1)に対し成り立つようにaの値をいくつか変えるとき、|a[i] - b[i](変更後のa[i])| / a[i]の最大値を最小化しろ、という問題。
　最大値の最小化ということで二分探索？という感じもしますがあまり探索しやすそうな式ではないです（でも、二分探索っぽい解答を見たのでいい感じに値をとると探索できるのかもしれません）。そこでdpを考えます。dp[i] := i番目までの最小値、としましょう。このとき、i - 1番目までの数列の一番後ろの数字が決まっていれば、dp[i]を簡単に決めることが出来ます。
　そこで、dp[i][j] = i番目までの部分数列a[0]...a[i]について、a[i] = j　となるような局所解　とします。
　こうすると、a[i + 1][j] = min(max(dp[i][k], a[i]→jへの遷移コスト))(kはjの約数)で更新できます。
　計算量の抑え方とかはちょっとテクニカルなので解説を見て下さい。
2011/Practice/夏合宿/講評 - ACM-ICPC Japanese Alumni Group
このページの3日目Fのところです。

コードはこんな感じ。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<double> a(N);
    for(auto& d : a) cin >> d;
    const int MAX = 150010;
    vector<double> dp(MAX, 0), tmp;
    rep(i, MAX) dp[i] = abs(a[0] - i) / a[0];
    REP(i, 1, N) {
        tmp.assign(MAX, 1.0e9);
        const int ub = (int)(1.5 * a[i] + 1.0);
        REP(k, 1, ub)
          for(int j = 1; k * j < ub; ++j) {
              double upd = max(dp[k] , abs(a[i] - k * j) / a[i]);
              tmp[k * j] = min(tmp[k * j], upd);
          }
        dp.swap(tmp);
    }
    cout << fixed << setprecision(10) << *min_element(dp.begin(), dp.end()) << endl;
    return 0;
}

　この問題のdp[i番目まで][最後の値がj]みたいにjがわかってると局所解がわかるから～みたいなdpよく見るんですけど毎回解けません。