为什么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

这个问题首先被分解成了两个问题：正向遍历，反向遍历。这一步应该不算是动态规划。但是两个小问题内部使用的就是动态规划算法了。每一小步都是一个递归的定义：已知前K天的最佳交易方式，那么当加入K+1天的价格，最佳交易方式是什么。K从0已知涨到N，于是就得到了前N天的最佳交易方式。