java - 为什么leetcode的这个题是一个动态规划?

Question

leetcode地址: https://leetcode.com/problems...

我对这个算法慢慢的还是可以想通的, 但是为什么他是动态规划呢? 动态规划不是要话分子问题, 列出递推方程的吗?但是这个题并不能列出递推方程的...还是说我思考的方式不对. 望指点一下这个算法的思想

public class BestTimeToBuyAndSellStockIII
{
    public int maxProfit(int[] prices)
    {
        if(prices.length == 0) return 0;
        int ans = 0;
        int n = prices.length;

        //正向遍历，opt[i]表示 prices[0...i]内做一次交易的最大收益.
        int opt[] = new int[n];
        opt[0] = 0;
        int low = prices[0];
        int curAns = 0;
        for(int i = 1; i < n; i++)
        {
            if(prices[i] < low)
                low = prices[i];
            else if(curAns < prices[i] - low)
                curAns = prices[i] - low;
            opt[i] = curAns;
        }

        //逆向遍历, opt[i]表示 prices[i...n-1]内做一次交易的最大收益.
        int optReverse[] = new int[n];
        optReverse[n - 1] = 0;
        curAns = 0;
        int high = prices[n - 1];
        for(int i = n - 2; i >= 0; i--)
        {
            if(prices[i] > high) high = prices[i];
            else if(curAns < high - prices[i]) curAns = high - prices[i];
            optReverse[i] = curAns;
        }

        //再进行划分，分别计算两个部分
        for(int i = 0; i < n; i++)
        {
            int tmp = opt[i] + optReverse[i];
            if(ans < tmp) ans = tmp;
        }
        return ans;
    }
}

Answer 1

Ce problème est d'abord décomposé en deux problèmes : le parcours avant et le parcours inverse.
Cette étape ne doit pas être considérée comme une programmation dynamique.

Mais les deux petits problèmes utilisent un algorithme de programmation dynamique en interne.
Chaque petite étape est une définition récursive : connaître la meilleure méthode de trading des K jours précédents, puis quelle est la meilleure méthode de trading en ajoutant le prix des K+1 jours.
K est connu pour passer de 0 à N, ce qui permet d'obtenir la meilleure méthode de trading pour les N jours précédents.