java - Python 到 C 算法

Question

我正在尝试找到更改算法的简单递归实现，我所能找到的就是 python 中的这个(有效)算法:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

我不了解 python，所以我正在寻求帮助，如果有人可以用 C 或 Java 重写这段小代码，以便我可以理解。或者，如果有人知道用 C 或 Java 实现此功能，您可以发布链接吗？

谢谢你的帮助

编辑: 我能够做到这一点:

int min_change(int * V, int C) {
    return min_coins(/*Length-last index*/, C)
}

int min_coins(int i, int C) {
    if (C == 0)return 0;
    else if (i == -1 || C < 0)return sizeof (int)*32;
    else return min(min_coins(i - 1, C), 1 + min_coins(i, C - V[i]));
}

Answer 1

我相信这是正确的等价物:

    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>

    int min_change0(int *V, int i, int aC)
    {
      if (aC == 0) {
        return 0;
      } else if (i == -1 || aC < 0) {
        return INT32_MAX - 1;
      } else {
        int a = min_change0(V, i-1, aC);
        int b = 1 + min_change0(V, i, aC - V[i]);
        return a <= b ? a : b;
      }
    }

    int min_change(int *V, int C)
    {
      int len = 0;
      while (V[len]) len++;
      /* min_coins(len(V)-1, C) */
      return len ? min_change0(V, len-1, C) : -1;
    }

    int main(void)
    {
      int total = 123;
      int values[] = {1,5,10,25,50,0 /* sentinel */};
      printf("minimal number of coins to change %i with 1, 5, 10, 25 and 50 coins is %i\n",
             total,
             min_change(values, total)
             );
      return 0;
    }

因为 2*50 + 2*10 + 3*1 是 123