前言

智障的我与动态规划

正文

问题来源

本问题来自字节跳动笔试题。当时我就觉得这道题满足最优子结构，但是没想到递推公式。笔试结束后，上网搜关于这道题的动态规划解法。

问题描述

给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，在给定一个整数aim代表要找的钱，求换钱有多少种方法。
如
arr=[1,5,10,25],aim=0,返回1
arr=[1,5,10,25],aim=15,返回6
arr=[3,5],aim=2,返回0

暴力递归破解法

如果arr=[5,10,25,1],aim=15
1.用0张5元货币，让[10,25,1]组成剩下的15,最终方法数记为res1
2.用1张5元货币，让[10,25,1]组成剩下的10,最终方法数记为res2
3.用2张5元货币，让[10,25,1]组成剩下的5,最终方法数记为res3
4.用3张5元货币，让[10,25,1]组成剩下的0,最终方法数记为res4
res1:2(0 * 5+15 * 1;0 * 5+1 * 10+1 * 5)
res2:2(1 * 5+10 * 1;1 * 5+1 * 10)
res3:1(2 * 5+5 * 1)
res4:1(3 * 5)
答案就是res1+res2+res3+res4

缺点：

大量重复计算。
规模小的时候还好，一旦规模大了。
比如aim=1000，对于05+110和25+010，后续的计算都是一样的，求[25,1]组合剩下的990的方法总数。
复杂度：
O(aim^N)

arr = [5, 10, 25, 1]
aim = 15
def naive_res_conis(arr, aim):
    def r(arr, aim, index):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            i = 0
            while arr[index] * i <= aim:
                res += r(arr, aim - arr[index] * i, index + 1)
                i += 1
        return res
    return r(arr, aim, 0)

经过记忆搜索优化的暴力递归

又如上面aim=1000的例子。
对于0 * 5+1 * 10和2 * 5+0 * 10，他们调用递归函数时候传入的参数，arr,aim,index都是相同的，也就是说我们可以利用这一性质去除重复的计算。
记忆搜索优化是针对暴力递归最初级的优化技巧，分析递归函数的状态可以由那些变量表示，做出相应维度和大小的cache即可。
复杂度:
O(N*aim^2)

from functools import wraps
def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap
def memo_res_conis(arr, aim):
    arr = arr
    @memo
    def r(aim, index):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            i = 0
            while arr[index] * i <= aim:
                res += r(aim - arr[index] * i, index + 1)
                i += 1
        return res
    return r(aim, 0)

Test

’’’
import time
aim=500
begin=time.time()
print memo_res(arr,aim)
print time.time()-begin
begin=time.time()
print naive_res(arr,aim)
print time.time()-begin
‘’’

结果

’’’ 19006 0.018000125885 19006 1.15899991989 ‘’’ ++++++++++++++++++++TEST END+++++++++++++++++++++++

动态规划（解法1）

dp[i][j]的含义，在可以任意使用arr[0…i]货币的情况下，组成j有多少种方法。
dp[…][0]:组成钱为0的方法数，全部置1
dp[0][…]:只能使用arr[0]的货币的情况下，组成钱的方法数
dp[1][…]:只能使用arr[0]与arr[1]的货币的情况下，组成钱的方法数
假设计算到位置(i,j),dp[i][j]的值可能来自下面的情况
1.完全不使用当前货币arr[i]的情况,即dp[i-1][j]
2.使用1张货币arr[i]的情况,即dp[i-1][j-arr[i]]
3.使用2张货币arr[i]的情况,即dp[i-1][j-2arr[i]]
….
k+1.使用k张货币arr[i]的情况,即dp[i-1][j-karr[i]] (j-k*arr[i]>=0)

复杂度：

枚举dp[i-1][0…j]上的所有值，dp一共有Naim个
O(Naim^2)
本质上，动态规划等价于记忆化搜索方法。
记忆话搜索的方法说白了就是不关心到达某一个递归过程的路径，只是单纯地对计算过的递归过程进行记录，避免重复的递归。
动态规划的方法则是规定好每一个递归过程的计算顺序，一次进行计算，后计算的过程严格依赖前面计算的过程。
动态规划规定计算顺序，而记忆搜索不用规定。各有各的优势
动态规划可以将递归变为迭代。记忆搜索面对某些情况，如arr=[20000,10000,1000],aim=2000000000的情况有优势 Python语言描述

def dp_coins(arr, aim):
    n = len(arr)
    dp = [[0] * (aim + 1) for i in range(n)]
    # 第一列全部置1
    for i in range(n):
        dp[i][0] = 1
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[0][arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            num, k = 0, 0
            while arr[i] * k <= j:
                # k=0时,也就是dp[i-1][j],也就是上一个元素
                # k=1时,也就是使用一张arr[i]货币的情况
                num += dp[i - 1][j - arr[i] * k]
                k += 1
            dp[i][j] = num
    return dp[-1][-1]

C语言描述

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<malloc.h>
int dp_find_money_way(int coinsValue[],int kindNum,int total)
{
	int i,j,k;
	int temp;
	int **dp = NULL;
	int result;
	//申请内存
	dp = (int **)malloc(sizeof(int *)*kindNum);
	for(i=0;i<kindNum;i++)
	{
		dp[i] = (int *)malloc(sizeof(int)*(total+1));
	}
	//初始化
	//dp[i][0]代表有，需要
	for(i=0;i<kindNum;i++)
	{
		dp[i][0] = 1;
	}	
	//dp[0][i]代表有，需要
	for(i=1;i<=total;i++)
	{		
		if(0==i%coinsValue[0])
		{
			dp[0][i] = 1;
		}
		else
		{
			dp[0][i] = 0;
		}		
	}
	//重点
	for(i=1;i<kindNum;i++)
	{
		for(j=1;j<=total;j++)
		{
			temp = 0;
			for(k=0; k*coinsValue[i]<=j;k++)
			{
				temp += dp[i-1][j-k*coinsValue[i]];
			}
			dp[i][j] = temp;
		}
	}	
	//存储结果
	result = dp[kindNum-1][total];
	
	//释放内存
	for(i=0;i<kindNum;i++)
	{
		free(dp[i]);
	}
	free(dp);
	return result;
}
int main()
{
	int arr[] = {5, 10, 25, 1,3};
	int aim = 100;
	//test
	printf("%d\n",dp_find_money_way(arr,5,aim));
    return 0;
}

动态规划的优化（解法2）

我们将目光放在前一个算法的第二个while循环里面。
本质上，while里面的枚举可以化简为dp[i][j]=dp[i-1][j]+dp[i][[j-arr[i]] (上边的加上左边的)
如，
arr = [5, 10, 25, 1]
aim = 25
dp[1][25]=dp[0]25+dp[i][[j-arr[i]] (用5块跟10块组成j-arr[i]元的方法数)
复杂度:
O(N*aim)

def dp_coin2(arr, aim):
    n = len(arr)
    dp = [[0] * (aim + 1) for i in range(n)]
    # 第一列全部置1
    for i in range(n):
        dp[i][0] = 1
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[0][arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            dp[i][j] = dp[i - 1][j]
            dp[i][j] += dp[i][j - arr[i]] if j - arr[i] >= 0 else 0
    return dp[-1][-1]

空间压缩
将空间复杂度降为O(aim)

def dp_coin3(arr, aim):
    n = len(arr)
    dp = [0 for i in range(aim + 1)]
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            dp[j] += dp[j - arr[i]] if j - arr[i] >= 0 else 0
    return dp[-1]
print dp_coin3(arr, aim)

结语

不管怎么样，都要坚持刷题，保证自己的脑袋不生锈。

换零钱的方法数

coin change

前言

正文