小编yix*_*ing的帖子

最近遇到一个算法问题，如下：

给定一个正整数数组，你可以选择数组中的任意连续区间，并将该区间内的每个数字减去相同的值，询问至少需要执行多少次上述操作才能使数组中的所有数字都为 0。

我正在尝试使用贪婪算法，但遇到了局部最小值问题，所以我意识到我必须使用动态规划，但我找不到递归公式，我的想法正确吗？如果不是，正确的思维方式是什么？谁能给我关于这个问题的提示吗？

我认真思考过这个问题，但我就是想不出结果，这让我很沮丧

编辑：

这是我的解决方案：使用贪心算法，每次选择区间内最小的数字，将区间内的每个数字减去该数字，递归地执行此操作，直到所有数字都为零。C++实现如下：

#include <iostream>
#include <vector>

using namespace std;

int foo(std::vector<int> &v, int l, int r) {
    int min = 0x3f3f3f3f;
    vector<int> idx;
    for (int i = l; i <= r; i++) {
        min = std::min(min, v[i]);
    }
    for (int i = l; i <= r; i++) {
        v[i] -= min;
        if (v[i] == 0) {
            idx.push_back(i);
        }
    }
    cout << "l: " << l << "r: " << r << " delete: " << …

我试图通过 Haskell 编写一个简单的解析器，但陷入了无限循环。代码是：

import Control.Applicative (Alternative, empty, many, (<|>))

data Parser a = Parser {runParser :: String -> [(a, String)]}

instance Functor Parser where
  fmap f (Parser p) = Parser $ \s -> [(f x', s') | (x', s') <- p s]

instance Applicative Parser where
  pure x = Parser $ \s -> [(x, s)]
  (Parser pf) <*> (Parser p) = Parser $ \s -> [(f' x, ss') | (f', ss) <- pf s, (x, ss') <- p ss]

instance …

我正在阅读Thinking with Types，第 4 章有一个问题：

type family AlwaysUnit a where
    AlwaysUnit a = ()

{- which a is ambiguous type? -}
AlwaysUnit a -> a
b -> AlwaysUnit a -> b
Show a => AlwaysUnit a -> String 

我知道Show a => AlwaysUnit a -> String有歧义类型，但我想知道为什么AlwaysUnit a -> a没有歧义类型？我无法将AlwaysUnit a -> a这种类型签名实现到函数中。

我已经学习了函子和单子的定义，但除了定义之外我仍然无法弄清楚它们之间的区别。我读过这个问题的一些答案，在Functor 和 Monad 之间有什么区别？一条评论说

函子采用纯函数（和函子值），而单子采用 Kleisli 箭头，即返回单子（和单子值）的函数。因此，您可以链接两个 monad，第二个 monad 可以依赖于前一个 monad 的结果。你不能用函子来做到这一点。

这个评论很有趣，让我了解了它们的区别。但我还有一些问题。

1. 为什么函子不能使用前一个函子的结果？因为fmap :: (a -> b) -> f a -> f b，当我fmap使用纯函数进行柯里化时，我可以获得一个f a -> f b函数，f b取决于，结果f a是否意味着函子内的数据？
2. 在范畴论中，我可以理解注释，因为我无法获取范畴论中的元素，但在Haskell中，我发现我可以使用函子的结果，因为Haskell可以记住数据构造函数，Haskell是否会阻止我理解此注释？我应该用纯范畴论来理解这一点吗？