动态规划算法的打印思路

2023-05-21

每次用动态规划求最佳值问题的时候，总会想到一个问题，该如何将每一种结果打印到控制台中呢？下面两段实例说不定会给你新的思路

零钱兑换I and 零钱兑换II

(1)零钱兑换I：

贪心算法

伪代码描述思想：

完全背包之求凑满背包的最少物品数:
容量->amount; 物品重量->coins[i]; 价值->1; 优化目标->求恰好凑满背包的物品最小价值
1.状态定义:dp[j]为凑满容量为j的背包所需最少物品数
2.状态转移:考虑coins[i]
    2.1 当j<coins[i]时:装不下,继承上一个dp[j]的值
    2.2 当j>=coins[i]时:可以装得下,可以选择装或者不装中价值小的(物品数小的)进行转移
        即:dp[j]=min(dp[j],dp[j-coins[i]+1])
3.初始化:容量为0,最少要装0个就可以装满->dp[0]=0,看转移方程,其他的要初始化为Integer.MAX_VALUE
4.遍历顺序:这里求最少的物品数,因此排列与组合均可,这里先物品后容量,物品顺序无所谓,容量必须正序(完全背包)
5.返回形式:返回如果dp[amount]有转移直接返回,如果没有转移返回-1

class Solution {
    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int coin : coins) {
            // 正序,j从coin开始即可
            for (int j = coin; j <= amount; j++) {
                // 前面dp值在有计算过的基础上才能转移
                if(dp[j - coin] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        // 有转移直接返回,没有转移说明凑不成返回-1
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

动态规划背包问题

递归公式->遍历顺序

(2)零钱兑换II：打印零钱兑换组合：

#include<stdio.h> 
#include<string.h>
//amou:未兑换为零钱的金额，step：步骤数组，len：步骤数，coins：零钱数组，m：零钱种类数，k：用于跳过重复组合的标志
void change(int amou , int *steps , int len , int *coins, int m ,int k){
        if(amou == 0){
            for(int i = 0 ; i < len ; i++ ){
                printf("%d " , steps[i]);
            }
            printf("\n");
        }
        for(int j = k ; j < m ; j++ ){
            if(amou >= coins[j]){

                steps[len] = coins[j];

                change(amou-coins[j] , steps , len+1 , coins , m, j );
            }
        }  
}

int change(int amount, int* coins, int coinsSize) {
    int dp[amount + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < coinsSize; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

int main(){
    int n=5;
    int steps[n];
    int coins[]={1,2,5};
    int count = change(n,coins,3) ;
    change(n,steps,0,coins,3,0);
    printf("%d兑换为零钱有以上%d种组合情况",n,count);
    return 0;
}

爬楼梯问题以及如何将组合数打印出来

使用递归函数打印所有可能的路径。我们可以修改动态编程解决方案，以跟踪到达每个楼梯所需的步骤。然后，我们可以使用递归函数根据所采取的步骤打印所有可能的路径。

printPaths函数有三个参数：n是要爬的剩余楼梯数，steps是迄今为止所走步骤的数组，len是步骤数组的长度。我们从一个空的steps数组开始，调用printPaths函数，其中n等于楼梯总数。根据下一步是1还是2，函数递归调用自身，n减少1或2。当n达到0时，我们打印步骤数组。

#include<stdio.h>
    void printPaths(int n, int *steps, int len) {//递归
    if (n == 0) {
        for (int i = 0; i < len; i++) {
            printf("%d ", steps[i]);
        }
        printf("\n");
    }
    if (n >= 1) {   //一步
        steps[len] = 1;
        printPaths(n-1, steps, len+1);
    }
    if (n >= 2) {  //两步
        steps[len] = 2;
        printPaths(n-2, steps, len+1);
    }
}            

void climbStairs(int n) {
    int dp[n+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    int steps[n];
    printPaths(n, steps, 0);
}

int main() {


    climbStairs(10);
    return 0;


}

tip：java参数传递与c参数传递

java中基本数据类型传值时不会影响主方法中的定义值的；而作为引用数据类型的数组（包括面向对象中的对象作为方法参数的时候）则会受到影响。

c语言中：

sizeof(a)无法得到数组的大小。为什么会这样？因为把数组作为参数传递给函数时，实际上只有数组的首地址作为指针传递给了函数。换句话说，在函数 **定义中的int a[]**等价于**int *a**。在只有地址信息的情况下，是无法知道数组里有多少个元素** 的。