动态规划

动态规划的核心：状态定义，状态转移方程

动态规划的想法

怎么把这两个东西想出来。

启发思路，回溯中子集型回溯，对于一个元素有选或不选两种思路。一些动态规划问题也可以用这两种思路来思考。

递归

打家劫舍。用递归的想法来考虑，问题的分解

思考过程：对于打家劫舍，可以先从边界开始思考，第一个或者最后一个的约束比较小，如果第 n 个不选，那么问题就变成了剩下 n - 1 个房子选或不选的问题。如果第 n 个选，那么问题就变成了剩下的 n - 2 个房子的问题。不断地重复下去。

回溯三问：

• 当前操作是什么？枚举第 i 个选/不选

• 子问题是什么？从前 i 个房子中获得最大金额和

• 下一个子问题？

  • 选：从前 i - 2 个中获得最大金额和

  • 不选：从前 i - 1 个中获得最大金额和

dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])

写程序之前想好入口参数和返回值是什么。回溯的时间负责度是指数级别，会超时，因此考虑优化。

记忆化搜索

递归搜索 + 保存计算结果 = 记忆化搜索。注意到 dfs 的计算，有时会传递进去相同的参数，但是还要展开计算。因此可以考虑记录一下计算值存储到 cache 数组。

这样的话递归的次数和节点数就是一样的，时间复杂度为 O(n)

优化后，时间复杂度和空间复杂度都是 O(n)

递推

算法中计算 max 发生在 dfs 函数调用结束后，也就是递归的归中才实际计算 max。

查看搜索树的话，使能看出从哪些点归回去的，那么就去掉递归中的递，只留下归。从下往上计算。

自上向下计算为记忆化搜索，自下向上计算就是递推。

记忆化搜索向递推的变换。

dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])

f[i] = max(f[i-1], f[i-2] + nums[i])

函数变数组，递归变循环。

这样的优化空间复杂度还是 O(n) 还可以接着优化。

f[i] 是现在要算的，f[i-1] 是上一个算出来的，f[i-2] 是上上个算出来的。也就是说，计算当前状态的，只需要知道上个状态的和上上个状态的，并不需要一整个数组。

0-1 背包问题

0-1 背包和完全背包是比较重要的 DP 模型，是选或不选思想的代表。

0-1 背包问题：

有 n 个物品，第 i 个物品的体积为 w[i]，价值为 v[i] ，每个物品最多选一个，求体积为 capacity 的背包能装下的最大价值是多少。

从递归开始思考

此问题的思考

• 当前操作：第 i 个物品选或不选。选了容量变小，不选容量不变。确定递归参数 i c

• 当前问题？剩余容量为 c 时，前 i 个物品价值最大

• 下一个问题？

  • 第 i 个选了：剩余容量为 c - w[i] 时，从前 i - 1 个物品价值最大

  • 第 i 个不选：剩余容量为 c 时，从前 i - 1 个物品价值最大

递归表达式

dfs(i, c) = MAX( dfs(i - 1, c - w[i]) + v[i], dfs(i - 1, c) )

代码实现

#define MAX(a, b)   (((a) > (b)) ? (a) : (b))

int capacity;
int *weight;
int *value;
int n;

// 返回价值
int bag01_dfs(int i, int c)
{
  if ( i < 0 )    return 0;
  if ( c < weight[i] )    return 0;
  return MAX(bag01_dfs(i - 1, c), bag01_dfs(i - 1, c - weight[i]) + value[i]);
}

int bag01(int capacity, int *weight, int *value) /* 返回最大价值 */
{
  return bag01_dfs(n - 1, capacity);
}

练习一下这个思路，leetcode 494 目标和。思考过程：把这个问题转化为选一些数添加负号满足一个值的背包问题。所有数和为 sum ，添加正号的数的和为 p，添加负号的数和为 q，有 p + q == sum，根据题目有 p - q = target，那么就有 2*p - sum = target，那么 p == (target + sum)/2 。通过一些数学上的计算，问题转化成从 nums 选一些数字，使得和为 (target + num)/2。

常见的变形问题：

• 1.最多装 c，求方案数、最大价值和

• 2.正好装 c，求方案数、最大价值和、最小价值和

• 3.最少装 c，求方案数、最小价值和

目标和这个题目转化后是正好装 c 的问题，要做的是把那个表达式改为加法。可以这么做的原因：选和不选两件事是互斥的，事件 A 或事件 B 发生的总数等于事件 A 的数量加上事件 B 的数量。

dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - w[i])

代码实现

#define MAX(a, b)   (((a) > (b)) ? (a) : (b))

int capacity;
int *weight;
int n;

int dfs(int i, int c)
{
    if ( i < 0 )
    {
        if (c == 0) return 1; 
        else         return 0;
    }          
    if ( c < weight[i] )  return dfs(i - 1, c);
    return dfs(i - 1, c) + dfs(i - 1, c - weight[i]);
}

int findTargetSumWays(int* nums, int numsSize, int target) {

    result = 0;
    n = numsSize;
    weight = nums;

    int sum = 0;
    for (int i=0; i<numsSize; i++)
        sum += nums[i];

    if ( ((target + sum)%2 == 1) || (target + sum < 0))     return 0;
    return dfs(n - 1, (target + sum)/2);
}

递推实现

去优化空间复杂度，递归改递推

dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - w[i])

f[i][c] = f[i - 1][c] + f[i - 1][c - w[i]]

f[i + 1][c] = f[i][c] + f[i][c - w[i]]

int findTargetSumWays1(int* nums, int numsSize, int target) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    
    int s = sum - abs(target);
    if (s < 0 || s % 2 != 0) {
        return 0;
    }
    
    int m = s / 2; // 背包容量

    int f[numsSize + 1][m];

    for (int c = 0; c <= m; c++) {
        f[0][c] = 0;
    }
    f[0][0] = 1; // 选择 0 个数字组成容量为 0 的方法数

    // 动态规划
    for (int i = 0; i < numsSize; i++) {
        for (int c = 0; c <= m; c++) {
            if (c < nums[i]) {
                f[i + 1][c] = f[i][c]; // 只能不选
            } else {
                f[i + 1][c] = f[i][c] + f[i][c - nums[i]]; // 不选 + 选
            }
        }
    }

    return f[numsSize][m];
}

使用了 C99 的 VLA 特性。也可以申请内存。

int** f = (int**)malloc((numsSize + 1) * sizeof(int*));
for (int i = 0; i <= numsSize; i++) {
    f[i] = (int*)malloc((m + 1) * sizeof(int));
}

// 初始化
for (int c = 0; c <= m; c++) {
    f[0][c] = 0;
}
f[0][0] = 1; // 选择 0 个数字组成容量为 0 的方法数

关于细节的处理，数组下标，边界条件转化为数组初始条件。

此二维数组的含义，表示从前 i 个数字中，选取若干个数字，使得它们的和等于 j 的方案数。

• i 表示前 i 个数字：i 的范围是从 0 到 numsSize。dp[i][j] 表示使用数组 nums 中的前 i 个数字（即 nums[0], nums[1], ..., nums[i-1]）去构造和为 j 的组合方案数。

• j 表示背包容量：j 的范围是从 0 到 m，表示通过这些数字能够构造出的和。

空间优化：两个数组

空间优化：一个数组

完全背包

完全背包问题：

有 n 种物品，第 i 种物品的体积为 w[i]，价值为 v[i] ，每种物品无限次选，求体积不超过 capacity 时的最大价值是多少。

递归三问

• 当前操作：第 i 种物品选或不选。选一个容量变小 w[i]，不选容量不变。确定递归参数 i c

• 当前问题？剩余容量为 c 时，前 i 种物品价值最大

• 下一个问题？

  • 第 i 种物品选一个：剩余容量为 c - w[i] 时，从前 i - 1 种物品价值最大

  • 第 i 种物品不选：剩余容量为 c 时，从前 i - 1 种物品价值最大

dfs(i, c) = MAX( dfs(i - 1, c), dfs(i, c - w[i]) + v[i] )

和 0-1 背包的区别，在选完一个物品以后，i 是不变的，还可以接着选。

leetcode 322 零钱兑换。这是完全背包的一个变形

完全背包问题的常见变形

• 至多装 capacity，求方案数、最大价值和

• 恰好装 capacity，求方案数、最大价值和、最小价值和

• 至少装 capacity，求方案数，最小价值和

递归实现

根据题目，要做适当的考虑

#define MAX(a, b)   (((a) > (b)) ? (a) : (b))
#define MIN(a, b)   (((a) < (b)) ? (a) : (b))

int capacity;
int *weight;
int n;

long long int dfs(int i, int c)
{
    if ( i < 0 )
    {
        if ( c == 0)    return 0;
        else            return LLONG_MAX;
    }
    if ( c < weight[i] )  return dfs(i - 1, c);
    return MIN(dfs(i - 1, c), dfs(i, c - weight[i]) + 1);
}

int coinChange(int* coins, int coinsSize, int amount) {
    n = coinsSize;
    weight = coins;
    long long int ans = dfs(n - 1, amount);
    
    if (ans == LLONG_MAX)   return -1;
    return ans;
}

对比这几个题目，要考虑返回值的问题，通常吧结果作为返回值。但是在边界判断的时候的常用技巧， C 种预定义的最大最小值，或者非负数的话把 -1 作为不满足条件的返回值。这里把 LLONG_MAX 作为没有合法方案的返回值。

递推实现，两个数组

上面的代码在 leetcode 里是超时的。

int coinChange(int* coins, int coinsSize, int amount) {
    weight = coins;
    n = coinsSize;
    long long int f[coinsSize + 1][amount + 1];
    for (int i=0; i<amount + 1;i++) f[0][i] = LLONG_MAX;

    f[0][0] = 0;

    for (int i = 0; i<coinsSize; i++)
    {
        for (int c=0; c<amount + 1; c++)
        {
            if (c < weight[i])  f[i + 1][c] = f[i][c];
            else                f[i + 1][c] = MIN(f[i][c], f[i+1][c - coins[i]] + 1);  
        }
    }

    int ans = f[n][amount];
    if ( ans == LLONG_MAX)
        return -1;
    return ans;
}

空间优化，两个数组和一个数组

变形问题总结

常见的变形问题：

• 1.最多装 c，求方案数、最大价值和

• 2.正好装 c，求方案数、最大价值和、最小价值和

• 3.最少装 c，求方案数、最小价值和

主要是边界条件的确定。