【算法】拼凑面额+数字和为sum的方法数+走网格（动态规划）

矫情吗；* 2022-06-08 02:18 212阅读 0赞

题目描述  
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N员（N为0-10000的非负整数）的不同组合的个数。  
输入描述:  
输入为一个数字N，即需要拼凑的面额  
输出描述:  
输出也是一个数字，为组成N的组合个数。  
示例1  
输入

5  
输出

一脸懵逼，记下来，慢慢研究

<?php
    //动态规划
    $n = trim(fgets(STDIN));
    
    $money = [1,5,10,20,50,100];
    
    $arr = [];
    
    $arr[0] = 1;
    
    for($i=0; $i<6; $i++){
            for($j = 1; $j<=$n; $j++){
                    if($j>=$money[$i]){
                            $arr[$j] =$arr[$j]+$arr[$j-$money[$i]];j值取和不取两种情况组合数目之和
                    }
            }
    }
    
    echo $arr[$n];

题目描述  
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。  
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。  
输入描述:

输入为两行:  
第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)  
第二行为n个正整数`A[i]`(32位整数)，以空格隔开。

输出描述:

输出所求的方案数

示例1

输入

5 15

5 5 10 2 3

输出

<?php
    
    $nsum = explode(' ', trim(fgets(STDIN)));
    
    $num = explode(' ', trim(fgets(STDIN)));
    
    $n = $nsum[0];
    $sum = $nsum[1];
    
    $dp[0][0] = 1;//$dp[$i][$j] 用i个数构成$j的
    
    for($i = 1; $i<=$n; $i++){
        for($j=0; $j<=$sum; $j++){
            $dp[$i][$j] = $dp[$i-1][$j];
            if($j>=$num[$i-1]){
                $dp[$i][$j] += $dp[$i-1][$j-$num[$i-1]];//用i-1个数构成$j的，加上用i-1个数构成$j-$num[i-1]的
            }
        }
    }
    
    echo $dp[$n][$sum];

注意，下面这句话，不好理解，我自己也想了半天

$dp[$i][$j] += $dp[$i-1][$j-$num[$i-1]];//用i-1个数构成$j的，加上用i-1个数构成$j-$num[i-1]的

举个例子

5 15

5 5 10 2 3

$dp[5][15] = 用四个数组成15的加上，用4个数组成12的（用四个数组成12的加上第五个数3，正好为15）

题目描述

有一个X\*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。  
输入描述:

输入包括一行，逗号隔开的两个正整数x和y，取值范围\[1,10\]。

输出描述:

输出包括一行，为走法的数目。

示例1  
输入

3 2  
输出

<?php
    
    $num = explode(' ', trim(fgets(STDIN)));
    
    $x = $num[0];
    $y = $num[1];
    
    $dp = [];
    
    for($i=0; $i<=$x; $i++){
       //一直往右走只有一种走法
        $dp[$i][0] = 1;
    }
    
    for($i=0; $i<=$y; $i++){
       //一直往下走也只有一种走法
        $dp[0][$i] = 1;
    }
    
    for($i=1; $i<=$x; $i++){
       //dp规律为$dp[$i][$j] = $dp[$i][$j-1] + $dp[$i-1][$j];他左边那个点的走法+他上边那个点的走法，就是他的走法
        for($j=1; $j<=$y; $j++){
            $dp[$i][$j] = $dp[$i][$j-1] + $dp[$i-1][$j];
        }
    }
    
    echo $dp[$x][$y];

注：从上往下思考问题，从下往上写代码。