[C++]面试题之动态规划类问题

• 问题问法:
  Q:现在有4种硬币，面值分别为1、2、5、10分，如果要组成一毛3可以有多少种组法?
  Q:一个人上台阶的时候一次可以跨1、2、5级台阶，如果台阶有13级他有多少种走法?
  实质都是求用n种数字组合成数值m

• 烧脑预警:
  因为我表达不太好，大家可能看的不是很懂，可以再看看
  https://blog.csdn.net/u013074465/article/details/48575585
  虽然我看这个文章时候也花了点时间想一些细节，毕竟这个问题真的三言两语讲不清楚
  如果往下的时候看不懂，回到下一行来看看这段话:
  ===========================================================================
  题目的问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum的所有组合数。
  设最后一种硬币的数量为xn。
  当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！
  xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp[i-1][sum -Vm]种;
  xn = 2 呢， dp[i-1][sum - 2 * Vm]种，等等。
  所有的这些情况加起来就是我们要求的dp[i][sum]。
  ===========================================================================

• 动态规划的概念:
  将一个多阶段问题转化成一系列的单阶段问题

• 转化讲解:
  用上面的问题做例子，用4种数字相加成目标值，多阶段的解法无非就是暴力枚举多层for循环镶嵌，
  这样很复杂也不是个聪明方法，但是把这一层一层for简化一下，转换一下思路
  比如你要求用2种数字组合成一个数值13(假设数字为1和2)，这里把用i种数值的组合成数值j的情况设为数组dp[i][j];
  那么其实就是
  dp[2][13]=dp[1][13-0x2]+dp[1][13-1x2]+dp[1][13-2x2]+...+dp[1][13-6x2];
  为什么是这样呢,我来解释下里面的意思，dp[1][13-0x2]这个就是当数字2的个数为0的时候的组合数，
  那么dp[1][13-1x2]就是当数字2的数量为1的时候的组合数，为什么到6就停了呢?因为用2去组合的话最多
  只能用6个2，7个的话2x7=14已经超过目标数值了，这里就是把多个阶段给分解成了一个阶段，也就将
  求法隐式地转成了利用数字2个数组合地可能性求答案。
  简化了一层for的求值:

    int target=13;
    int last_coin=2;
    for(int k=0;k<=target/last_coin;++k)
    {
        dp[last_coin][target]+=dp[last_coin-1][target-k*last_coin];
    }

看完代码就有人会问，那d[1][target-k*last_coin]的值从哪里来?那当然是根据d[0][target-k * last_coin]的值累积来的,那么d[0][target-k * last_coin]的值又从哪里来?朋友们，0的时候是在求问题“用0种硬币求目标数值可能性有多少种”的答案了，答案当然是1，你要用0种硬币求一个数值，那么所有的组合只有一种，数值是0，各种硬币的数量也为0.

• 代码

#include<iostream>
using namespace std;
int main(){
    int coins[4]={1,2,5,10};//硬币种类数组
    const int coin_kinds_num=sizeof(coins)/sizeof(coins[0]);
    const int total=13;//要组合成的目标数值
    /*以上为条件：硬币种类和要组合成的目标数值*/
    int dp[coin_kinds_num][total+1];
    for(int i=0;i<coin_kinds_num;i++)
    {
        dp[i][0]=1;
    }
    /*以上为初始化特殊情况(后面计算要用)当要组合成的目标数值为0的时候，只有一种情况，那就是各种硬币的搭配都是0个*/
    for(int i=1;i<=coin_kinds_num;++i)//这里i从1开始,因为已经跳过了特殊情况，而且也不会组合目标数值0
    {
        for(int j=1;j<=total;++j)//
        {
            dp[i][j]=0;//数组未初始化的时候值是随机数，这里初始化一下
            for(int k=0;k<=j/coins[i-1];++k)//这里的j/coins[i-1]是指用i种硬币去组合目标时,最多可以放多少个coins[i-1]这种硬币
            {
                dp[i][j]+=dp[i-1][j-k*coins[i-1]];
            }
        }
    }
    return 0;
}