uq_27405755260

用户名：uq_27405755260

访问量：266

签　名：

等　　级
排　　名	50589
经　　验	282
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

动态规划求解
浏览：182

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

动态规划求解

　　作者: uq_27405755260　　　　发表时间：2021-03-13 15:48:52 浏览：182　|　评论：0　

原题链接：K-进制数

# 动态规划求解
  动态规划一般用于求解最值问题。本题可以将题意转化为：N位数字最多能表示多少K进制数。
## 初步解法
我们使用二维数组dp[N][2]来记录状态，其中dp[i][0]表示i位数，以0结尾的数字数量；dp[i][1]表示i位数，不以0结尾的数字数量
显然：dp[i][0] = dp[i - 1][1]，因为如果第i位数字想填0，那么第i-1位数字就不能为0；
同样，dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (K - 1)，因为如果第i位数字不填0，那么对前i-1位数字没有要求，所以为其总和。
代码如下：
```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
		int[][] dp = new int[N][2]
		dp[1][0] = 0;//只有一位数字的情况，不能为0
		dp[1][1] = K - 1;//可以为除0以外的K-1位数
        for (int i = 2; i <= N; i++) {
			dp[i][0] = dp[i - 1][1];
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (K - 1);
        }
		//输出以0结尾和不以0结尾的数字总和
        System.out.println(dp[N][0] + dp[N][1]);
    }

}
```
## 空间优化
可以看出，在进行迭代的过程中，状态转移只与dp[i - 1][0] 和dp[i - 1][1]相关，所以，我们用变量dp_0和dp_1来记录，进行滚动变化，可以将空间复杂度降为O(1)。
代码如下：
```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int dp_0 = 0;
        int dp_1 = K - 1;
        for (int i = 2; i <= N; i++) {
            int tmp = dp_0;
            dp_0 = dp_1;
            dp_1 = (tmp + dp_1) * (K - 1);

}
        System.out.println(dp_0 + dp_1);
    }

}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

uq_27405755260

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

【矩阵】（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

动态规划求解

评论区

精彩推荐

Biggest Number （C++代码）回溯法

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

打水问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-拆分位数（C++代码）

1051（奇了怪了）

C二级辅导-阶乘数列（C语言代码）

Hello, world! （C语言代码）

1134题解(求分析)

简单的a+b （C语言代码）

uq_27405755260

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

【矩阵】 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

逆反的01串 （C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

动态规划求解

评论区

精彩推荐

Biggest Number （C++代码）回溯法

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

打水问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-拆分位数 （C++代码）

1051（奇了怪了）

C二级辅导-阶乘数列 （C语言代码）

Hello, world! （C语言代码）

1134题解(求分析)

简单的a+b （C语言代码）

【矩阵】（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

　　评论区

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

打水问题（C语言代码）

WU-拆分位数（C++代码）

C二级辅导-阶乘数列（C语言代码）