If You Knew Tomorrow’s Stock Prices—— Dynamic Programming in Trading

· · 个人记录

If You Knew Tomorrow’s Stock Prices — Dynamic Programming in Trading

Introduction

Suppose you knew the exact stock prices for every day of the next few months. Would it then be easy to decide when to buy and sell?

Knowing the future removes uncertainty, but it does not remove the difficulty of decision-making. When every choice changes the possibilities of future choices, finding the optimal strategy becomes an algorithmic problem.

This article explains how dynamic programming finds the most profitable trading strategy without trying every possible sequence of trades.

From Trading Decisions to Mathematical Models

We follow a few trading rules. The account can hold up to P shares at a time. After buying or selling, we must wait W full days before trading again. For example, if W=1 and we trade on day 1, we can next trade on day 3.

Besides P and W, suppose we also know the stock prices for the next T days.

We begin with no shares and enough money to cover our purchases. The buying price is at least the selling price on each day. The goal is to maximize the final profit: the total money received from sales minus the total money spent on purchases.

A straightforward idea is to enumerate every possible sequence of buying and selling. However, the number of possible strategies can grow exponentially with time, making this approach impractical even for relatively short periods.

The key observation is that many different trading histories can lead to the same situation.

For example, suppose two strategies reach the same day with the same number of shares, and both have finished their waiting periods. From then on, they have the same trading options. If one has earned less than the other, it cannot produce a better final result by following the same future trades.

This leads to the central idea of dynamic programming:

We do not need to remember every past transaction. We need to keep the information that affects future decisions.

Defining the State

To describe a trading situation, we only need two pieces of information:

Let dp[i][j] represent the maximum profit after day i, when we own exactly j stocks.

Initially, we have no stocks and no profit:

dp[0][0]=0

All unreachable states are assigned:

-\infty

because they cannot contribute to any valid solution.

We can now solve the problem by using state transitions to calculate dp[i][j] from earlier states.

State Transition

On each day, there are three possible actions.

1. Do Nothing

If we do not trade today, the number of shares remains unchanged. We first set:

dp[i][j]=dp[i-1][j].

We then check whether buying or selling can give a better result.

2. Buying Shares

If we buy on day i, the previous transaction must have happened no later than day i-W-1.

Assume that before buying we owned k shares. After buying j-k shares, our net cash income becomes:

dp[p][k]-(j-k)AP_i.

Therefore, for every valid k, we update:

dp[i][j] \leftarrow \max\left\{ dp[i][j], dp[p][k]-(j-k)AP_i \right\},

where:

\max(0,j-AS_i)\le k<j.

This range ensures that we buy at least one share and no more than today's buying allowance.

3. Selling Shares

Similarly, if we sell k-j shares on day i, we update:

dp[i][j] \leftarrow \max\left\{ dp[i][j], dp[p][k]+(k-j)BP_i \right\},

where:

j<k\le\min(P,j+BS_i).

These three cases cover every legal trading schedule. If a transaction happens today, all earlier transactions must finish by day p, so their best result is already available in the table.

The final answer is:

dp[T][0].

There is no benefit to ending with unsold shares when we count only cash income: omitting the purchases of those leftover shares would save money without changing the completed sales.

There are O(TP) states, and each state checks at most O(P) previous holdings. The total running time is:

O(TP^2).

The table uses O(TP) memory, or about 8TP bytes with 64-bit integers. When TP^2 is around 10^7 or less, the computation will typically finish within about a second on a modern computer.

The Bigger Picture

Our DP finds the maximum profit without checking every possible sequence of trades. By reusing the best results for earlier states, it avoids much of the repeated work in brute-force enumeration.

To run it, we need T, the number of days; P, the maximum number of shares we can hold; and W, the number of full days we must wait after each transaction. For each day i, we also need the buying and selling prices, AP_i and BP_i, and the maximum quantities we can buy and sell, AS_i and BS_i. When TP^2 is around 10^7 or less, this approach is usually fast enough for a short run on a modern computer.

Here is a C++ implementation you can try in VS Code with a C++ compiler installed. This version allows up to 500 days and 500 shares. You can increase the array size by changing N in the code, keeping it larger than both T and P. However, large values of TP require more memory, and large values of TP^2 take longer to compute.

Enter T, P, and W on the first line, followed by T lines containing AP_i, BP_i, AS_i, and BS_i.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const ll INF=1e18;
int t,p,w,ap,bp,as,bs;
ll dp[N][N];

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t>>p>>w;
    for (int i=0;i<=t;i++)
        for (int j=0;j<=p;j++) dp[i][j]=-INF;
    dp[0][0]=0;

    for (int i=1;i<=t;i++) {
        cin>>ap>>bp>>as>>bs;
        int pre=max(0,i-w-1);
        for (int j=0;j<=p;j++) {
            dp[i][j]=dp[i-1][j];
            for (int k=max(0,j-as);k<j;k++) {
                if (dp[pre][k]==-INF) continue;
                dp[i][j]=max(dp[i][j],
                            dp[pre][k]-1ll*(j-k)*ap);
            }
            for (int k=j+1;k<=j+min(bs,p-j);k++) {
                if (dp[pre][k]==-INF) continue;
                dp[i][j]=max(dp[i][j],
                            dp[pre][k]+1ll*(k-j)*bp);
            }
        }
    }
    cout<<dp[t][0]<<'\n';
    return 0;
}

The program prints the maximum profit after T days.

Beyond trading, dynamic programming helps businesses plan inventory and reduce ordering and storage costs. It is also used to calculate shortest paths in networks and align DNA sequences to identify similarities. The states and transitions change, but reusing earlier results remains central to each application.