好吧,要解决任何动态规划问题,您需要将其分解为重复出现的子解决方案。
假设我们将您的问题定义为 A(n, k),它通过从 n 中删除 k 位返回可能的最大数字。
我们可以由此定义一个简单的递归算法。
使用您的示例, A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }
更一般地说,A(n, k) = max { A(n with 1 digit removed, k - 1) }
你的基本情况是 A(n, 0) = n。
使用这种方法,您可以创建一个缓存 n 和 k 值的表。
int A(int n, int k)
{
typedef std::pair<int, int> input;
static std::map<input, int> cache;
if (k == 0) return n;
input i(n, k);
if (cache.find(i) != cache.end())
return cache[i];
cache[i] = /* ... as above ... */
return cache[i];
}
现在,这是直截了当的解决方案,但是有一个更好的解决方案可以使用非常小的一维缓存。考虑将问题改写成这样:“给定一个字符串 n 和整数 k,在长度为 k 的 n 中找到字典序上最大的子序列”。这本质上就是您的问题,解决方案要简单得多。
我们现在可以定义一个不同的函数B(i, j),它给出长度为(i - j)的最大词典序列,仅使用n的前i位(换句话说,从前i位中删除了j位n ) 。
再次使用您的示例,我们将拥有:
B(1, 0) = 1
B(2, 0) = 12
B(3, 0) = 123
B(3, 1) = 23
B(3, 2) = 3
等等
稍微思考一下,我们可以找到递推关系:
B(i, j) = max( 10B(i-1, j) + n i , B(i-1, j-1) )
或者,如果j = i那么B(i, j) = B(i-1, j-1)
和B(0, 0) = 0
您可以以与上述非常相似的方式对其进行编码。