金融科技導論 DP
===

    free_cash = 1000

    # Dp table:
    days, num_stock = priceMat.shape
    dp_table = np.zeros((days, num_stock+1))
    back_track = np.zeros((days, num_stock+1))

    # Dp path: need a extra day for 0-th day.
    path = np.zeros(days+1)
    path[days] = num_stock

    FROM_CASH = num_stock
    for i_stock in range(num_stock):
        # Use init free_cash try all-in each stock.
        dp_table[0][i_stock] = free_cash*(1-transFeeRate)/priceMat[0][i_stock]
        back_track[0][i_stock] = FROM_CASH

    KEEP_CASH = num_stock
    dp_table[0][KEEP_CASH] = free_cash

    # Doing Dp: by the point-to-next indexing.
    for day in range(1, days):
        prices_today = priceMat[day]

        # Calculate max stock for all possible to_stock.
        for to_stock in range(num_stock):
            stock_from_method = np.zeros(num_stock+1)
            for from_stock in range(num_stock):
                if from_stock == to_stock:
                    stock_from_method[from_stock] = dp_table[day-1][from_stock]
                else:
                    stock_from_method[from_stock] = \
                        dp_table[day-1][from_stock] * prices_today[from_stock] * (1-transFeeRate)\
                        * (1-transFeeRate) / prices_today[to_stock]
            stock_from_method[KEEP_CASH] = dp_table[day-1][KEEP_CASH] * (1-transFeeRate) / prices_today[to_stock]
            # By np.max and np.argmax, we can find the best method to maximize the stock for to_stock.
            dp_table[day][to_stock] = np.max(stock_from_method)
            back_track[day][to_stock] = np.argmax(stock_from_method)

        # Calculate max cash from all possible pre-states
        cash_from_method = np.zeros(num_stock+1)
        for from_stock in range(num_stock):
            cash_from_method[from_stock] = dp_table[day-1][from_stock] * prices_today[from_stock] * (1-transFeeRate)
        cash_from_method[KEEP_CASH] = dp_table[day-1][KEEP_CASH]
        dp_table[day][KEEP_CASH] = np.max(cash_from_method)
        back_track[day][KEEP_CASH] = np.argmax(cash_from_method)

    # Back track: Last day
    last_day_cash = np.zeros(num_stock+1)
    for from_stock in range(num_stock):
        last_day_cash[from_stock] = dp_table[days-1][from_stock] * priceMat[days-1][from_stock] * (1-transFeeRate)
    last_day_cash[KEEP_CASH] = dp_table[days-1][KEEP_CASH]

    prev_stock = np.argmax(last_day_cash)
    current_method = KEEP_CASH

    # Result: a (k, 4) matrix that contains k transaction records.
    actionMat = []

    for day in range(days-1, 0, -1):
        if current_method == KEEP_CASH:
            if prev_stock != current_method:
                action = [day, int(prev_stock), -1, 8922099]
                actionMat.append(action)
        else:
            if prev_stock != current_method and prev_stock != KEEP_CASH:
                action = [day, int(prev_stock), current_method, 8922099]
                actionMat.append(action)

            elif prev_stock != current_method and prev_stock == KEEP_CASH:
                action = [day, -1, current_method, 8922099]
                actionMat.append(action)
        current_method = int(prev_stock)
        prev_stock = back_track[day - 1][current_method]

    actionMat.reverse()
    return actionMat