算法设计------Dynamic Pragraming 1-dimensional

发表于 | 分类于

算法设计——Dynamic Pragraming 1-dimensional

举个栗子

问题：给定n，求 将n 表达为1，3，4的和的写法数量

例如 n = 5 , 答案是：6

5 = 1 + 1 + 1 + 1 + 1

5 = 1 + 1 + 3

5 = 1 + 3 + 1

5 = 3 + 1 + 1

5 = 1 + 4

5 = 4 + 1

分析

以Dn表示，将n表达为1，3，4的和的数量。

假定n = x1 + x2 + · · · + xm

如果xm = 1,其他项的总和为n-1

则，以xm = 1结尾的和的数目等于 Dn-1

以此类推的xm = 3 , xm = 4 分别为 Dn-3,Dn-4

公式

从上述分析中可得到公式

  • D0 = 1;
  • Dn = Dn−1 + Dn−3 + Dn−4;

实现

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int count (int * arr, int m , int n){
    
    if (n == 0) {
        return 1;
    }
    
    if (n < 0) {
        return 0;
    }
    
    int counts = 0;
    
    for (int i = 0; i < m; i ++) {
        counts += count(arr, m , n - arr[i]);
    }

    return counts;
}

测试代码

1
2
3
int array[] = {1,3,4};
int count_5 = count(array, 3, 5);
printf("count_5 == %d",count_5);

执行结果

1
count_5 == 6

相关链接

以下链接给出了在不关心元素位置时该问题的解

Dynamic Programming | Set 7 (Coin Change)

如果对你有帮助的话，Star✨下一吧！