Java教程

【926. 将字符串翻转到单调递增】动态规划

本文主要是介绍【926. 将字符串翻转到单调递增】动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！ 
class Solution {
    public int minFlipsMonoIncr(String s) {
        int len = s.length();
        int[][] dp = new int[len][2];
        if (s.charAt(0) == '0') {
            dp[0][0] = 0;
            dp[0][1] = 1;
        } else {
            dp[0][1] = 0;
            dp[0][0] = 1;
        }

        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == '1') {
                dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]);
                dp[i][0] = dp[i-1][0] + 1;
            }else{
                dp[i][1] = Math.min(dp[i-1][0]+1,dp[i-1][1]+1);
                dp[i][0] = dp[i-1][0];
            }
        }

        return Math.min(dp[len - 1][1], dp[len - 1][0]);
    }
}

 

这篇关于【926. 将字符串翻转到单调递增】动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航