java动态编程（如何以最有效的方式发送消息）

Question

我在动态规划方面遇到了困难，我是这方面的新手，所以我希望您能在任何方面帮助我，问题是：

作为IKS B'Moth克林贡战斗巡洋舰的通信官，您的职责是以最有效的方式管理通信。假设您需要传输消息S=s1。。。sm以m符号的字符串形式给出。为此，您有r个不同的代码。设b（ij）为在第j代码中编码消息的第i个符号所需的位数。最初，网桥发送器设置为代码#1，但您可以在消息中的任何位置自由更改代码，并根据需要更改任意次数。要做到这一点，如果您想从当前代码i切换到任何其他代码j，您需要发送一个由C（ij）位组成的控制代码。您的目标是确定如何以最有效的方式（使用最少的位数）发送电子邮件

A）证明问题具有最优子结构

B）找到所需最佳位数的重复周期

C）建立一个自下而上的动态规划算法来解决该问题，并指出其复杂性

Answer 1

您可以创建一个三维数组，并使用previousCode、newCode和ithSymbol作为索引。当扫描到ithSymbol并且当它将代码从previousCode切换到newCode时，数组将存储最少的位

递归公式为：

dp(ithSymbol, previousCode, newCode)=min_(i=1 to r)(dp(ithSymbol-1,i,previousCode))+C(previousCode, newCode)+b(ithSymbol,newCode); 

（假设C（i，i）=0表示所有i）

现在您可以自己编写代码了

注意，这是一种幼稚的方法。通过将数组设置为2-D，可以进一步提高效率，因为在任何步骤中都只使用ithSymbol-1